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

按递归来实现:

  • 按一定的规律从字符串s中取子串,
  • 比较确定子串是否存在词库dict中,
    • 若存在,将字符串s除去该子串的剩余部分作为新的字符串s;
    • 若不存在,则返回false。

具体的实现方法

1:
  • 使用contains()方法判断子串是否存在词库dict中,
  • 剩余部分的长度逐次减小至s.length() == 0,未返回false,说明所取子串存在词库dict中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static boolean WordBreak(String s,Set<String> dict) {
if (s.length()==0)
return true;
for(int i=1; i <= s.length(); i++) {
String first = s.substring(0, i);//取子串的规律
String remain = s.substring(i);
if (dict.contains(first) && WordBreak(remain, dict) ) {
System.out.print(first + " ");//返回存在词库dict中的子串
return true;
}
}
return false;
}
2:
  • 使用equals()方法判断子串是否存在词库dict中,
  • 取子串的起点逐次后移至start == s.length(),未返回false,说明所取子串存在词库dict中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static boolean WordBreak(String s, Set<String> dict){
return WordBreakHelper(s, dict, 0);
}
public static boolean WordBreakHelper(String s, Set<String> dict, int start){
if(start == s.length())
return true;
for(String word: dict){//取子串的规律
int end = start + word.length();
if(end > s.length())//IndexOutOfBoundsException
continue;
if(s.substring(start, end).equals(word))//equals()方法
return WordBreakHelper(s, dict, end);
}
return false;
}

这里的equals()方法是比较两个变量所引用的字符串的内容是否相等,与其功能类似的==则是比较两个变量是否指向同一个字符串。同样,使用“”使新的变量获得了一个字符串的引用,而使用String()构造器则创建了一个新的字符串对象。

通过下面的示例程序对上述总结做进一步说明:

1
2
3
4
5
6
7
String x = "world";
String y = new String("word");
String z = new String("world").intern();
System.out.println(x.equals(y));//true
System.out.println(x == y);//false
System.out.println(x == z);//true

参考资料:

Leetcode Solution – Word Break

Create Java String Using ” ” or Constructor?