【leetcode】字符串分割

题目：Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s ="leetcode",dict =["leet", "code"]. Return true because"leetcode"can be segmented as"leet code".

英语要是不大好，似乎题目都读不懂了。。。
给定一个字符串和一个词典dict，确定s是否可以根据词典中的词分成 一个或多个单词。比如，给定 s = “leetcode” dict = [“leet”, “code”] 返回true，因为"leetcode"可以被分成"leet code"。

思路：
按照动态规划算法的思路，先找状态F(i)：前i个字符能否被分割。
递推公式：F(i) = F(j) && substr[j+1,i]（j<i）能在字典中找到。什么意思呢，就是在j<i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，则F(i)为true。
初始状态为：F(0) = true
返回结果：F(n)
用题中的例子来说：
F(1)："" && “l” —> false
F(2)："" && “le”，“l” && “e” —> false
F(3)："" && “lee”，“l” && “ee”，“le” && “e” —> false
F(4)： j=0,"" && “leet” —> true
　　　j=1,“l” && “eet” —> false
　　　j=2,“le” && “et” —> false
　　　j=3,“lee” && “t” —> false
…
以此类推，新建一个数组保存中间F(i)的值，外层循环控制F(i)，内层循环控制[0~i)分割的结果。
具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ZiFuChuanFenGe {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s.length() <= 0) {
            return false;
        }
        if (dict.isEmpty()) {
            return false;
        }
        boolean[] arr = new boolean[s.length() + 1];
        //初始化F(0)为true
        arr[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] && dict.contains(s.substring(j, i))) {
                    arr[i] = true;
                    break;
                }
            }
        }
        return arr[s.length()];
    }
}

最后

以上就是爱笑钥匙最近收集整理的关于【leetcode】字符串分割的全部内容，更多相关【leetcode】字符串分割内容请搜索靠谱客的其他文章。