139. Word Break.md

139. Word Break

Problem

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

Solution

方法一： 分支限界法（记忆化搜索)

java

    public boolean wordBreak(String s, Set<String> wordDict) {
        return helper(s, wordDict, new HashMap<String, Boolean>());
    }
    
    boolean helper(String s, Set<String> wordDict, Map<String, Boolean> map) {
        if(map.containsKey(s)) return map.get(s);
        if(s.length()==0) return true;
        boolean res = false;
        for(String word : wordDict) {
            if(s.startsWith(word)) {
                res |= helper(s.substring(word.length()), wordDict, map);
            }
        }
        map.put(s, res);
        return res;
    }

go

方法二： 动态规划（效果不太好，可能与数据集有关）

设dp[i]表示长度i的字串是否能够划分， 则:

dp[i] = dp[i-j] 如果字串ij在词典中(0=<j<=i)

java

public boolean wordBreak(String s, Set<String> wordDict) {
	boolean[] dp = new boolean[s.length()+1];
	dp[0] = true;
	for(int i=1; i<dp.length; i++) {
		for(int j=i; j>=0&&!dp[i]; j--){
			if(wordDict.contains(s.substring(i-j,i))) dp[i] = dp[i-j];
		}
	}
	return dp[dp.length-1];
}