Leetcode139. 单词拆分

题目传送： https://leetcode.cn/problems/word-break/

运行效率：

代码如下：

class Solution {
    //map用于提升查询性能
   Map<String,Boolean> map= new HashMap();
  public boolean wordBreak(String s, List<String> wordDict) {
   for(String item:wordDict){
     if(s.startsWith(item)){
       String restStr = s.substring(item.length());
       if("".equals(restStr)){
         return true;
       }
       if(map.containsKey(restStr)){
         return map.get(restStr).booleanValue();
       }else{
         boolean b = wordBreak(restStr, wordDict);
         map.put(restStr, b);
         if(b){
           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