BudiBadu Logo

Lantern Vowel Pathways

Dynamic Programming Hard 0 views
Like6

Lantern artisans arrange tiles with lowercase letters on a rectangular board A runner starts at the top-left and moves only Right or Down until reaching the bottom-right To keep the light melody gentle vowels a e i o u must appear in Nondecreasing Alphabetical Order consonants can appear anywhere Your task in Lantern Vowel Pathways is to count all valid paths The secret sauce here is State-Based DP As you navigate the grid you track the last vowel encountered to ensure the next one doesn''t violate the melody Consonants don''t change the state but vowels must be equal to or greater later in the alphabet than the previous one If a path contains no vowels it automatically satisfies the rule Return the total count modulo 1 000 000 007 This helps the festival coordinate multiple runners for the nightly showcases It s a beautiful way to practice pathfinding with sequence-based constraints in a professional grid-based layout When the task involves connectivity or route cost build adjacency carefully and guard against revisiting stale states Use a visited or best-distance structure to avoid repeated work and ensure unreachable scenarios return the required fallback value instead of partial traversal results At hard difficulty hidden tests usually combine scale with edge behavior so the implementation must be both asymptotically efficient and logically strict Define transitions unambiguously prevent stale-state contamination and confirm tie-breaking or fallback rules are encoded directly in the core algorithm For implementation

Examples

Example 1
Input
grid = ["bc", "df"]
Output
2
Explanation

Both paths contain no vowels, so they automatically satisfy the rule.

Example 2
Input
grid = ["ab", "oo"]
Output
2
Explanation

Paths "a->b->o->o" and "a->o->o" both have vowels in nondecreasing order.

Example 3
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.

Algorithm Flow

Recommendation Algorithm Flow for Lantern Vowel Pathways - Budibadu
Recommendation Algorithm Flow for Lantern Vowel Pathways - Budibadu

Best Answers

java
class Solution {
    public int count_vowels(String s) {
        int count = 0;
        String vowels = "aeiouAEIOU";
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) != -1) count++;
        }
        return count;
    }
}