Word Break

问题描述

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". 

解决思路

1. dfs，超时；

2. dp。

使用一个大小为输入字符串长度加1的辅助数组，dp[i]表示S[0, i]字符串是否可以被分割。

双重for循环，时间复杂度为O(n^2).

程序

1. DFS

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }
        if (wordDict == null || wordDict.size() == 0) {
            return false;
        }
        return helper(s, wordDict);
    }
    
    private boolean helper(String s, Set<String> wordDict) {
        if (s.length() == 0) {
            return true;
        }
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            String word = s.substring(0, i + 1);
            if (wordDict.contains(word)) {
                flag = helper(s.substring(i + 1), wordDict);
            }
        }
        return flag;
    }
}

2. DP

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }
        if (wordDict == null || wordDict.size() == 0) {
            return false;
        }
        return helper(s, wordDict);
    }
    
    private boolean helper(String s, Set<String> wordDict) {
        if (s.length() == 0) {
            return true;
        }
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            String word = s.substring(0, i + 1);
            if (wordDict.contains(word)) {
                flag = helper(s.substring(i + 1), wordDict);
            }
        }
        return flag;
    }
}

　　

WordBreakII

问题描述

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"]. 

解决思路

还是动态规划的思路，区别问题I的是，dp[i]代表以i为结尾的，能够break的单词，由于单词数可能有多个，所以是一个list数组。

程序

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return res;
        }
        
        int len = s.length();
        List<String>[] dp = new ArrayList[len + 1];
        dp[0] = new ArrayList<String>();
        
        for (int i = 1; i <= len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                String word = s.substring(j, i);
                if (!wordDict.contains(word) || dp[j] == null) {
                    continue;
                }
                if (dp[i] == null) {
                    dp[i] = new ArrayList<String>();
                }
                dp[i].add(word);
            }
        }
        
        if (dp[len] == null) {
            return res;
        }
        
        String sol = "";
        helper(res, sol, dp, len);
        return res;
    }
    
    private void helper(List<String> res, String sol, List<String>[] dp, int end) {
        if (end < 0) {
            return ;
        }
        if (end == 0) {
            String solution = new String(sol);
            res.add(solution.trim());
            return ;
        }
        
        for (String word : dp[end]) {
            helper(res, word + " " + sol, dp, end - word.length());
        }
    }
}