leetcode — word-break

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;/**
* Source : https://oj.leetcode.com/problems/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".
*
*/
public class WordBreak { /**
* 判断给定的字符串是否能分割为多个单词，每个单词都包含在给定的字典中
*
* 1. 使用DFS，如果能到达字符串最后，说明可以break
* 2. 题目中只是判断是否的问题，并不需要求出具体break的方法，对于是否的问题可以使用DP来解决
*
* dp[i]:表示str[i-1]能否被break，比如dp[1]表示str[0:0]能否被break
* dp[0] = true
* dp[i] = true,当：
* 存在0 <= k <= i-1, dp[k] = true, 并且tr[k:i-1] 存在dic中
*
* @param str
* @param dic
* @return
*/
public boolean wordBreak (String str, Set<String> dic) {
boolean[] dp = new boolean[str.length()+1];
dp[0] = true;
for (int i = 0; i < str.length(); i++) {
for (int j = i; j > -1; j--) {
if (dp[j] && dic.contains(str.substring(j, i+1))) {
dp[i + 1] = true;
break;
}
}
}
return dp[str.length()];
} public static void main(String[] args) {
WordBreak wordBreak = new WordBreak();
String[] dicStr = new String[]{"leet", "code"};
boolean result = wordBreak.wordBreak("leetcode", new HashSet<String>(Arrays.asList(dicStr)));
System.out.println(result + " == true");
}
}