BudiBadu Logo

Luminous Script Segmentation Count

Dynamic Programming Hard 1 views
Like15

Luminous Script Segmentation Count is a counting version of word-break style parsing You receive a continuous script string and a dictionary of valid phrases and your job is to count how many different ways the script can be split into valid dictionary tokens A segmentation is valid only when every character is consumed in order and each chunk exists in the phrase set If nothing matches the full string the answer is zero The practical approach is dynamic programming on prefix length Let dp i represent the number of valid ways to segment the first i characters Start with dp 0 1 then for each position try extending with dictionary words or check all previous cuts and add compatible counts Because the number of segmentations can explode quickly every addition must be taken modulo 1 000 000 007 The judge checks ambiguous strings with multiple valid cuts impossible strings and edge behavior where the input may be short or effectively empty Determinism matters same input must always return the same count Keep the function focused on counting not reconstructing paths This challenge is a great hard-level practice for prefix DP substring matching efficiency and strict modular arithmetic discipline under combinational growth For performance prune impossible cuts early and reuse cached prefix counts 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

Examples

Example 1
Input
script = "lanternfair", phrases = ["lan","lantern","tern","fair"]
Output
1
Explanation

The script can be restored as "lantern fair" or "lan tern fair".

Example 2
Input
script = "riverlights", phrases = ["river","light","lights","riverlight"]
Output
2
Explanation

Only the segmentation "river lights" matches the script.

Example 3
Input
script = "", phrases = ["lantern"]
Output
1
Explanation

The empty script has one valid segmentation that uses no phrases.

Algorithm Flow

Recommendation Algorithm Flow for Luminous Script Segmentation Count - Budibadu
Recommendation Algorithm Flow for Luminous Script Segmentation Count - Budibadu

Best Answers

java
import java.util.*;
class Solution {
    public int count_segmentations(String s, String[] dictionary) {
        Set<String> words = new HashSet<>(Arrays.asList(dictionary));
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (words.contains(s.substring(j, i))) {
                    dp[i] += dp[j];
                }
            }
        }
        return dp[n];
    }
}