Fork me on GitHub

Word Break && Word Break II

Posted on

Linkage

https://leetcode.com/problems/word-break/description/

https://leetcode.com/problems/word-break-ii/description/

Analysis

In the first question, we just need to count the combination of wordBreak, but in the second question, we need to find out all the combination. To avoid TLE crisis because of a tricky case in Word Break II, we need to judge the first in advance.

Question I: Word Break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] ret = new boolean[s.length()+1];
        if (wordDict.size() == 0 || s.length() == 0) return false;
        
        ret[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            ret[i] = false;
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength) continue;
                if (s.substring(i - wordLength, i).equals(word) && ret[i - wordLength] == true) 
                    ret[i] = true;
            }
        }
        return ret[s.length()];
    }
}

Question II: Word Break II

Naive code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashMap<Integer, LinkedList<String> > map = new HashMap<Integer, LinkedList<String> >();
        LinkedList<String> firstList = new LinkedList<String>();
        firstList.add(new String(""));
        map.put(0, firstList);
        for (int i = 1; i <= s.length(); i++) {
            LinkedList<String> ret_i = new LinkedList<String>();
            
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength || s.substring(i-wordLength, i).equals(word) == false) continue;
                List<String> wordListStringList = map.get(i - wordLength);
                if (wordListStringList == null) continue;
                for (String wordListString : wordListStringList) {
                    String space = ( i == s.length() ? "": " "); 
                    String newWordListString = wordListString + word + space;
                    ret_i.add(newWordListString);
                }
            }
            map.put(new Integer(i), ret_i);
        }
        List<String> ret = map.get(s.length());
        return ret;
    }
}

To pass a very tricky but unmeaningful false case, we should judge whether there is a path prior to find path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public boolean whetherWordBreak(String s, List<String> wordDict) {
        boolean[] ret = new boolean[s.length()+1];
        if (wordDict.size() == 0 || s.length() == 0) return false;
        
        ret[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            ret[i] = false;
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength) continue;
                if (s.substring(i - wordLength, i).equals(word) && ret[i - wordLength] == true) 
                    ret[i] = true;
            }
        }
        return ret[s.length()];
    }
    
    
    public List<String> wordBreak(String s, List<String> wordDict) {    
        if ( whetherWordBreak(s, wordDict) == false )
            return new LinkedList<String>();
        
        HashMap<Integer, LinkedList<String> > map = new HashMap<Integer, LinkedList<String> >();
        LinkedList<String> firstList = new LinkedList<String>();
        firstList.add(new String(""));
        map.put(0, firstList);
        
        
        for (int i = 1; i <= s.length(); i++) {
            LinkedList<String> ret_i = new LinkedList<String>();
            
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength || s.substring(i-wordLength, i).equals(word) == false) continue;
                List<String> wordListStringList = map.get(i - wordLength);
                if (wordListStringList == null) continue;
                for (String wordListString : wordListStringList) {
                    String space = ( i == s.length() ? "": " "); 
                    String newWordListString = wordListString + word + space;
                    ret_i.add(newWordListString);
                }
            }
            map.put(new Integer(i), ret_i);
        }
        List<String> ret = map.get(s.length());
        return ret;
    }
}

So ugly!!!