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 38
| import java.util.*;
public class 单词拆分_139 { public static void main(String[] args) { } public Map<String, Boolean> map = new HashMap<>(); public boolean wordBreak(String s, List<String> wordDict){
boolean[] dp = new boolean[s.length() + 1];
for(String word:wordDict){ map.put(word, true); }
dp[0] = true;
for(int i=1;i<s.length();i++){ for(int j=i-1;j>=0;j--){ dp[i] = dp[j] && check(s.substring(j, i)); if(dp[i]) break; } } return dp[s.length()]; } public boolean check(String s){ return map.getOrDefault(s, false); } }
|