Lantern Vowel Pathways
The lantern artisans arrange glowing tiles in a rectangular board, each tile etched with a lowercase letter. A ceremony runner starts at the board's top-left corner and may move only right or down, collecting letters along the way until reaching the bottom-right tile. To keep the melody of lights gentle, the runner only accepts paths in which the vowels (a, e, i, o, u) they encounter appear in nondecreasing alphabetical order; consonants are always allowed. The coordinator wants to count how many valid paths satisfy this rule so the ceremonial chant matches the board's harmony.
You receive the grid of letters as a list of strings of equal length. Consider only paths that move right or down. For each path, ignore consonants and examine the subsequence of vowels encountered; it must be sorted alphabetically (repeats allowed) to qualify. Return the number of valid paths modulo 1_000_000_007. If either dimension is zero, treat the board as having zero paths. Construct the answer with dynamic programming, optionally tracking vowel states, and refrain from altering the board. Empty vowel sequences automatically satisfy the constraint.
This tally helps the festival schedule multiple runners, balance lighting sequences, and plan which boards harmonize best with nightly music. Provide the modded count so the crew can confirm the ceremony, plan backups, and let the audience experience the quiet rise of lantern tones.
Example 1:
Input: grid = ["ab", "oo"]
Output: 2
Explanation: Paths "a->b->o->o" and "a->o->o" both have vowels in nondecreasing order.
Example 2:
Input: grid = ["ae", "ia"]
Output: 1
Explanation: Only the path "a->e->a" is valid; the other paths include the letter sequence e followed by i, which violates nondecreasing order.
Example 3:
Input: grid = ["bc", "df"]
Output: 2
Explanation: Both paths contain no vowels, so they automatically satisfy the rule.
Related Problems
No related problems found
Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this problem.
