leetcode 139 字符串按词典分割

佚名 6年前 (2019-04-22) 随笔 1177人围观抢沙发百度已收录

题意：

判断一个字符串是否可以分割成若干个子串（单词），使得每个单词都可以在字符串列表（词典）中找到。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路一：

回溯（递归）。一开始想到的解法（可能也是因为最近类似解法的题做的有点多），非常简单直观，但是效率低，超时。

 1 class Solution {
 2     public boolean wordBreak(String s, List<String> wordDict) {
 3         return helper(s, 0, wordDict);
 4     }
 5     
 6     public boolean helper(String s, int start, List<String> dict) {
 7         if (start >= s.length()) {
 8             return true;
 9         }
10         boolean tmp = false;
11         for (String item : dict) {
12             if (s.indexOf(item, start) == start) {
13                 tmp = tmp || helper(s, start + item.length(), dict);
14             }
15         }
16         return tmp;
17     }
18 }

思路二：

dp（动态规划）。为了重复利用递归过程中的一些结果，提高效率，所以改用dp。

 1 class Solution {
 2     public boolean wordBreak(String s, List<String> wordDict) {
 3         int n = s.length(); //这里输入都是非空的，n >= 1
 4         boolean[] opt = new boolean[n + 1];
 5         opt[n] = true; //opt[i]表示从i到n - 1的子串是否为wordBreak。opt[n]初始化为true
 6         for (int i = n - 1; i >= 0; i--) {
 7             opt[i] = false;
 8             for (String item : wordDict) {
 9                 if (s.indexOf(item, i) == i) {
10                     opt[i] = opt[i] || opt[i + item.length()];
11                 }
12                 
13                 //如果已经为true就可以不用再匹配wordDict里的字符串了
14                 if (opt[i]) {
15                     break;
16                 }
17             }
18         }
19         return opt[0];
20     }
21     
22 }