LeetCode 139. 单词拆分(记忆化搜索 dp

基本上是参考这一篇：https://leetcode-cn.com/problems/word-break/solution/shou-hui-tu-jie-san-chong-fang-fa-dfs-bfs-dong-tai/

一个关键点在于：判断其中一部分如果在词典中，那么只要递归的判断剩下一部分即可

可以很快写出一个简单的搜索：

class Solution { // 思路 前一部分是词典里的单词 那么将后一部分继续递归判断 private boolean helper(String s,int pos,HashSet<String> dict){ if(pos==s.length()){ return true; } for(int i=pos+1;i<=s.length();i++){ String pre=s.substring(pos,i); if(dict.contains(pre)&&helper(s,i,dict)){ return true; } } return false; } public boolean wordBreak(String s, List<String> wordDict) { return helper(s,0,new HashSet<>(wordDict)); } }

超时

原因很简单：

因为这里的重复计算是判断i开头的字符串是否breakable，所以这里可以对其做一个memo，去掉重复计算

class Solution { // 思路 前一部分是词典里的单词 那么将后一部分继续递归判断 private Boolean[] Break; private boolean helper(String s,int pos,HashSet<String> dict){ if(pos==s.length()){ return true; } if(Break[pos]!=null){ return Break[pos]; } for(int i=pos+1;i<=s.length();i++){ String pre=s.substring(pos,i); if(dict.contains(pre)&&helper(s,i,dict)){ Break[pos]=true; return true; } } Break[pos]=false; return false; } public boolean wordBreak(String s, List<String> wordDict) { Break=new Boolean[s.length()]; return helper(s,0,new HashSet<>(wordDict)); } }