文章目录
  1. 1. 递归
  2. 2. DP
  3. 3. 扩展
    1. 3.1. DFS
  4. 4. 参考

【题目】: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”.

递归

看到网上很多人说使用递归的方式来做这道题目,大致代码如下:

public boolean wordBreak(String s, Set<String> dict) {
    return wordBreakHelper(s, dict, 0);
}

private boolean wordBreakHelper(String s, Set<String> dict, int start) {
    if (dict == null)
        return true;
    if (dict.isEmpty())
        return false;

    if (s == null)
        return false;

    if (start >= s.length())
        return true;

    for (String temp : dict) {
        int end = start + temp.length();

        if (end > s.length())
            continue;

        if (s.substring(start, end).equals(temp)) {
            return wordBreakHelper(s, dict, end);
        }
    }


    return false;
}

实际上这个是不能被Accepted的,比如

s = "abcd"
dict = ["abc", "a", "b", "cd"]

其实这个是满足要求的,但是s在匹配到abc的时候index直接跳到了3,也就是d的位置,然后后面就没有办法匹配了。

DP

Define an array t[] such that

t[i]==true => 0-(i-1) can be segmented using dictionary

Initial state t[0] == true

public boolean wordBreak(String s, Set<String> dict) {
    boolean[] dp = new boolean[s.length()+1];
    dp[0] = true;

    for (int i=0; i< s.length(); i++) {
        if (!dp[i])
            continue;

        for (String temp : dict) {
            int end = temp.length() + i;
            if (end > s.length())
                continue;
            if (dp[end])
                continue;

            if (s.substring(i, end).equals(temp)) {
                dp[end] = true;
            }
        }
    }

    return dp[s.length()];
}

扩展

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is [“cats and dog”, “cat sand dog”].

DFS

DFS+HASH记忆

public List<String> wordBreak(String s, Set<String> dict) {
    HashMap<String, List<String>> map = new HashMap<String, List<String>>();
    if (s == null || s.length() == 0 || dict == null) {
        return null;
    }

    return dfs(s, dict, map);
}

private List<String> dfs(String s, Set<String> dict, HashMap<String, List<String>> map) {
    if (map.containsKey(s)) {
        return map.get(s);
    }

    List<String> list = new ArrayList<String>();
    int len = s.length();

    if (len == 0) {
        list.add("");
    } else {
        // i 表示左边字符串的长度
        for (int i = 1; i <= len; i++) {
            String sub = s.substring(0, i);

            // 左边的子串可以为空,或是在字典内
            if (!dict.contains(sub)) {
                continue;
            }

            // 字符串划分为2边,计算右边的word break.
            List<String> listRight = dfs(s.substring(i, len), dict, map);


            // 把左字符串加到右字符串中,形成新的解.
            for (String r: listRight) {
                StringBuilder sb = new StringBuilder();
                sb.append(sub);
                if (i != 0 && i != len) {
                    // 如果左边为空,或是右边为空,不需要贴空格
                    sb.append(" ");
                }
                sb.append(r);
                list.add(sb.toString());
            }
        }
    }

    map.put(s, list);
    return list;
}

参考

More https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dp/WordBreak2.java

文章目录
  1. 1. 递归
  2. 2. DP
  3. 3. 扩展
    1. 3.1. DFS
  4. 4. 参考