BudiBadu Logo
00:00

Lantern Vowel Pathways

Dynamic Programming Easy 0 views

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.

BudiBadu Logo

Lantern Vowel Pathways

Dynamic Programming Easy 0 views

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.

00:00
Loading editor...
Test Results

Run your code to see test results

Click the Submit button to execute your solution

Related Problems

No related problems found

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.