leetcode-word-break

发表于   |   分类于 ，   |  

题目大意

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

　　给你一个目标字符串和一个字符串的List，问目标字符串是否可以被字符串的List中的若干个分解而来，已知字符串数组无重复的字符串。

注意题目中的注释，方法的第二个参数已由原来的Set<String>换成了List<String>

题目分析

　　动态规划，可以用记忆化搜索实现，我写的版本代码比较长（实际上其中一部分是二分查找）。思路是：先将List进行排序，然后对目标字符串从前往后开始搜索，对于搜索的当前位置idx，字符是str.charAt(idx)用这个字符做为字符串的首字符，在List中进行二分查找，对查找到的结果进行遍历，看哪一个可以作为前缀，然后继续向下搜索。

　　第二种方法，参考了讨论区里的解法，虽然解法依据的是Set<String>，但是可以进行二分改造一下，主体的思想还是动态规划，可以看下代码。

代码

　　第一种解法：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Solution {
    private int[] f;
    private String str;
    private List<String> words;
    private int len;
    
    // 二分查找，大于等于ch的最小index
    private int startSearch(char ch) {
        int left = -1;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (words.get(mid).charAt(0) >= ch) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
    
    // 二分查找，小于等于ch的最大index
    private int endSearch(char ch) {
        int left = 0;
        int right = len;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (words.get(mid).charAt(0) <= ch) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private boolean search(int idx) {
        if (idx > str.length() - 1) {
            return true;
        }
        if (f[idx] > 0) {
            return f[idx] == 1;
        }
        String t = str.substring(idx);
        int start = startSearch(str.charAt(idx));
        int end = endSearch(str.charAt(idx));
        if (start > end || start < 0 || start >= len || end < 0 || end >= len) {
            f[idx] = 2;
            return false;
        }
        for (int i = start; i <= end; i++) {
            if (t.startsWith(words.get(i))) {
                if (search(idx + words.get(i).length())) {
                    f[idx] = 1;
                    return true;
                }
            }
        }
        f[idx] = 2;
        return false;
    }
    
    public boolean wordBreak(String s, List<String> wordDict) {
        len = wordDict.size();
        f = new int[s.length()];
        str = s;
        Collections.sort(wordDict);
        words = wordDict;
        return search(0);
    }
}

　　复杂度：O(m * lgn * n *len)，m是s的长度，n是数组长度

　　第二种解法：

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
public class Solution {
    
    private List<String> words;
    
    private boolean search(String str) { // 二分查找str
        int left = -1;
        int right = words.size(); // 左右区间为开开
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int comp = words.get(mid).compareTo(str);
            if (comp > 0) {
                right = mid;
            } else if (comp < 0) {
                left = mid;
            } else {
                return true;
            }
        }
        return false;
    }
    
    public boolean wordBreak(String s, List<String> wordDict) {
        
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        words = wordDict;
        Collections.sort(words);
        for (int i = 1; i <= s.length(); i++) { // i为字符串长度
            for (int j = 0; j < i; j++) {
                if (f[j] && search(s.substring(j, i))) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.length()];
    }
}

　　复杂度：O(m * m * lgn * len)