|
单词拆分
回溯法
普通的递归会超时，因为有大量的递归重复计算，所以我们可以使用记忆化搜索，创建一个memory数组，如果开始下标之后的字符串无法拆分，把该位置设为true，递归调用到的话直接返回，这种算法时间复杂度是O(n ^ 3)，因为substring的时间复杂度是O（n），其实还可以再提速，把这里优化掉，我们可以使用字符串哈希算法，原理很简单，给你一个很长的字符串可能存不下和很长的数字可以存下，后者所占的空间会少很多，但主要还是为了方便判断一个字符串是否出现过，这是最基础的部分。 具体算法可以参考字符串哈希
class Solution {
boolean[] memory;
public boolean wordBreak(String s, List wordDict) {
//这道字符串拆分可以联想到回溯法暴力拆分，但是有可能超时，所以我们这里使用记忆化搜索
Set set = new HashSet(wordDict);
this.memory = new boolean[s.length()];
return backTracking(s,set,0);
}
public boolean backTracking(String s,Setset,int startIndex) {
if(s.length() == 0) return true;
if(memory[startIndex]) return false;
for(int i = 0;i |