139. Word Break

leetcode-cn Daily Challenge on June 25th, 2020.

leetcode Daily Challenge on September 29th, 2020.

Difficulty : Medium

Related Topics : Dynamic Programming

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

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

You may assume the dictionary does not contain duplicate words.

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

Solution

mine

Java

DFS && Memorize Runtime: 4 ms, faster than 84.66%, Memory Usage: 39.1 MB, less than 87.05% of Java online submissions

//O(N^2)time  O(N)space
public boolean wordBreak(String s, List<String> t) {
    //remove the same string in t
    Set<String> wordDictSet = new HashSet(t);
    List<String> wordDict = new ArrayList<>(wordDictSet);
    //record  substring result
    HashMap<String, Boolean> record = new HashMap<>();
    //remove substring not contains
    for (int i = wordDict.size() - 1; i >= 0; i--) {
        if (!s.contains(wordDict.get(i))) {
            record.put(wordDict.get(i), false);
            wordDict.remove(i);
        }
    }
    return helper(s, wordDict, record);
}

public boolean helper(String s, List<String> wordDict, HashMap<String, Boolean> record) {
    if (record.containsKey(s)) {
        return record.get(s);
    }
    int i;
    for (String word : wordDict) {
        boolean res = true;
        if ((i = s.indexOf(word)) != -1) {
            if (i > 0) {
                String before = s.substring(0, i);
                boolean b = helper(before, wordDict, record);
                if (b) {
                    record.put(before, true);
                }
                res = b;
            }
            if (i + word.length() < s.length()) {
                String end = s.substring(i + word.length());
                boolean b = helper(end, wordDict, record);
                if (b) {
                    record.put(end, true);
                }
                res = res && b;
            }
            if (res) {
                record.put(s, true);
                return res;
            }
        }
    }
    record.put(s, false);
    return false;
}

DP Runtime: 5 ms, faster than 82.26%, Memory Usage: 37 MB, less than 99.99% of Java online submissions

same as https://leetcode-cn.com/problems/re-space-lcci/;

// O(N * S) time 
// O(N)space
// N = s.length()  S = wordDict's char count
public boolean wordBreak(String s, List<String> wordDict) {
    int len = s.length();
    int dp[] = new int[len + 1];
    for(int i = 1; i <= len; i++){
        dp[i] = dp[i - 1] + 1;
        String t = s.substring(0,i);
        for(String word : wordDict){
            if(word.length() <= i  && t.endsWith(word)){
                dp[i] = Math.min(dp[i], dp[i - word.length()]);
            }
        }
    }
    return dp[len] == 0;
}

DP & Trie Runtime: 2 ms, faster than 95.13%, Memory Usage: 40.1 MB, less than 21.03% of Java online submissions

// O(N * M) time  M = Min(N, max word.length() in wordDict)
// O(N + S)space
// N = s.length()  S = wordDict's char count
public boolean wordBreak(String s, List<String> wordDict) {
    Trie trie = new Trie();
    for(String word : wordDict){
        trie.insert(word);
    }
    int len = s.length();
    char[] arr = s.toCharArray();
    int dp[] = new int[len + 1];
    for(int i = 1; i <= len; i++){
        dp[i] = dp[i - 1] + 1;
        Trie t = trie;
        for(int j = i - 1; j >= 0; j--){
            int index = arr[j] - 'a';
            t = t.next[index]; 
            if(t == null){
                break;
            }
            if(t.hasValue){
                dp[i] = Math.min(dp[i], dp[j]);
            }
        }
    }
    return dp[len] == 0;
}

class Trie{
    public Trie[] next = new Trie[26];
    public boolean hasValue;

    public void insert(String s){
        Trie t = this;
        char[] arr = s.toCharArray();
        for(int i = arr.length - 1; i >= 0; i--){
            int index = arr[i] - 'a';
            if(t.next[index] == null){
                t.next[index] = new Trie();
            }
            t = t.next[index];
        }
        t.hasValue = true;
    }
}

the most votes

Runtime: 1 ms, faster than 99.01%, Memory Usage: 37.8 MB, less than 94.92% of Java online submissions

//O(N^2)time  O(N)space
public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<String> set = new HashSet<>();
    int max = Integer.MIN_VALUE;
    for (String str : wordDict) {
        max = Math.max(str.length(), max);
        set.add(str);
    }
    HashMap<Integer, Boolean> map = new HashMap<>();
    return getResult(s, 0, set, max, map);
}

private boolean getResult(String s, int start, HashSet<String> set, int max, HashMap<Integer, Boolean> map) {
    if (start == s.length()) {
        return true;
    }
    if (map.containsKey(start)) {
        return map.get(start);
    }
 
    for (int i = start; i < start + max && i < s.length(); i++) {
        if (set.contains(s.substring(start, i + 1))) {
            if (getResult(s, i + 1, set, max, map)) {
                map.put(start, true);
                return true;
            }
        }
    }
    map.put(start, false);
    return false;
}

the leetcode solution

Backtrack & Memorize Runtime: 5 ms, faster than 81.73%, Memory Usage: 40 MB, less than 23.47% of Java online submissions

//O(N^2)time  O(N)space
public boolean wordBreak(String s, List<String> wordDict) {
    return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
}
public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
    if (start == s.length()) {
        return true;
    }
    if (memo[start] != null) {
        return memo[start];
    }
    for (int end = start + 1; end <= s.length(); end++) {
        if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
            return memo[start] = true;
        }
    }
    return memo[start] = false;
}

BFS Runtime: 7 ms, faster than 51.03%, Memory Usage: 39.4 MB, less than 71.41% of Java online submissions

//O(N^2)time  O(N)space
public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet=new HashSet(wordDict);
    Queue<Integer> queue = new LinkedList<>();
    int[] visited = new int[s.length()];
    queue.add(0);
    while (!queue.isEmpty()) {
        int start = queue.remove();
        if (visited[start] == 0) {
            for (int end = start + 1; end <= s.length(); end++) {
                if (wordDictSet.contains(s.substring(start, end))) {
                    queue.add(end);
                    if (end == s.length()) {
                        return true;
                    }
                }
            }
            visited[start] = 1;
        }
    }
    return false;
}

DP Runtime: 6 ms, faster than 70.31%, Memory Usage: 39.5 MB, less than 57.72% of Java online submissions

//O(N^2)time  O(N)space
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()];
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

139. Word Break.md

139. Word Break.md

139. Word Break

Example 1:

Example 2:

Example 3:

Solution

Files

139. Word Break.md

Latest commit

History

139. Word Break.md

File metadata and controls

139. Word Break

Example 1:

Example 2:

Example 3:

Solution