问题描述
给定一个字符串和一个字符串列表，要求判断是否能将字符串分割成列表中的字符串，列表中的字符串可以重复使用。题目链接：**点我**
样例输入输出
输入：s = “applepenapple”, wordDict = [“apple”, “pen”]
输出：true
输入：s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出：false
问题解法
解法一：递归（超时）
直接使用递归的做法，每次遍历字符串列表，判断剩余的字符串是否有以字符串列表中的字符串开头的，如果有，则移动查找的指针到下个位置（指针移动距离为匹配的字符串长度），继续下一轮搜索，如果搜索指针移动到最后，则说明原始字符串能切割成功，否则说明切割不成功。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution
{
public boolean wordBreak(String s, List<String> wordDict)
{
return wordBreak(s, 0, wordDict);
}
private boolean wordBreak(String str, int startIndex, List<String> wordDict)
{
if (startIndex == str.length())
{
return true;
}
for (String word : wordDict)
{
if (str.indexOf(word, startIndex) == startIndex)
{
boolean isFind = wordBreak(str, startIndex + word.length(), wordDict);
if (isFind)
{
return true;
}
}
}
return false;
}
}
|
解法二：递归+剪枝
解法一中直接用递归，虽然简单，但是超时了，原因是可能存在重复搜索的过程。因此，增加一个数组记录当前位置是否搜索过，如果已经搜索过，则直接返回结果，不重复进行，从而达到剪枝的效果，也称之为记忆化搜索。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution
{
public boolean wordBreak(String s, List<String> wordDict)
{
int[] flags = new int[s.length() + 1];
return wordBreak(s, 0, flags, wordDict);
}
private boolean wordBreak(String str, int startIndex, int[] flags, List<String> wordDict)
{
if (startIndex == str.length())
{
return true;
}
if (flags[startIndex] == -1)
{
return false;
}
for (String word : wordDict)
{
if (str.indexOf(word, startIndex) == startIndex)
{
boolean isFind = wordBreak(str, startIndex + word.length(), flags, wordDict);
if (isFind)
{
return true;
}
flags[startIndex] = -1;
}
}
return false;
}
}
|