BudiBadu Logo

Luminous Script Segmentation Count

Dynamic Programming Hard 1 views
Like15

At the riverside festival, the stage manager receives a continuous script string describing lantern cues for the evening showcase. Each cue is one of several rehearsed phrases stored in the troupe's dictionary, but the printing press dropped the spaces between words when the parchment got damp. Before lighting rehearsals begin, the manager needs to know in how many distinct ways the script can be segmented into valid phrases so every department confirms their cue and how often the combinations branch.

You will receive the condensed script as a lowercase string and a list of distinct lowercase phrases that represent valid cues. Reusing phrases is allowed, and the order of words must respect the original string. Because the number of segmentations can explode for longer scripts, return the total modulo 1_000_000_007. Leave both the script and dictionary untouched; build the answer with dynamic programming rather than enumerating every partition by hand, and treat an empty script as a single calm segmentation that uses no words at all.

This quick calculation tells the festival planner whether the script is unambiguous, how many rehearsal branches to schedule, and which lantern teams should stay on call. Provide the modded count so the stage manager can finalize cue sheets, warn musicians about alternate sequences, and deliver a confident briefing before the dress rehearsal begins.

Example 1:

Input: script = "lanternfair", phrases = ["lan","lantern","tern","fair"]
Output: 2
Explanation: The script can be restored as "lantern fair" or "lan tern fair".

Example 2:

Input: script = "riverlights", phrases = ["river","light","lights","riverlight"]
Output: 1
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];
    }
}