Word Break

Info

📖 139. Word Break

Description

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

Thinking

• Understand following characteristics:
  • Repeatable selection
  • Not cover all elements
  • Disorder of selection.
• Multiple Results & Not consider how it processes
• Longest substring ? ❌ Tree ? ❔ DP ? ❔
• Remaining Match ✅. Gradually match from str head.

Solution

Recursion & Prunning

Recursion

We need a full rigth path (but actually don’t need a path) to match the target String s. So based on the principle from left to right, we can try to match words from the beginning of the target string.

Like: ApplePenYes
Apple: PenYes
Pen: Yes
Yes: Finished.

So this solution surely bases on Recursion. So there may exist problem of overtime-calculating.

Steps

Foreach word dictionary, see if there is a word match the beginning of the target string.

1. Matched: See if it is the last word for target String.
   1. No: Substring the target String, then do the same thing.
   2. Yes: Find a right match case.
2. Not Matched: Try to match another word.

Pruning

Important

Solution will cost extremly long time when facing this case:

Target String: “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab”

WordDict: ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

So we need to do some pruning actions to improve performance of this solution.

Thoughts

We can ensure that if a string can be matched by giving words, so that’s what we gonna do.

So: Building a global set to hold strings which can not be matched by giving words, and we will try to look it up when facing a new string that needs to be matched.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return recursion(new HashSet<>(), s, wordDict);
    }

    public boolean recursion(HashSet<String> failSet, String s, List<String> wordDict) {
        boolean result = false;
        // Pruning
        if (failSet.contains(s)) {
            return false;
        }
        for (String word: wordDict) {
            if (s.length() > word.length() && s.substring(0, word.length()).equals(word)) {
                result = recursion(failSet, s.substring(word.length()), wordDict);
            } else if (s.equals(word)) {
                return true;
            }
            // IMPORTANT
            if (result) {
                return true;
            }
        }
        // Memorable(for pruning)
        failSet.add(s);
        return result;
    }
}

Result-1

DP (Copy)

Withought pruning optimazation.

Core

If DP[i-j] == true && s.substring(j, i) matches a word in dictionary, then dp[i] is good.

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

Result-2

Reflection

• When doing recursion, be sure to check if you need to return true/false when finding answers. Need to check the previous recursion step to see if it’s successfully returns the right result.