leetcode 139. Word Break 动态规划

题意

输入：(String s, List wordDict) 输出：s是否可有wordDict中的单词拼凑而成。可以重复使用。

思路

动态规划，一维数组存前n位所组成的字符串的结果。 dp[n] = 任意一个i < n，有dp[i] && 右边的字符串在wordDict中出现。

解1

// Runtime: 6 ms, faster than 64.73% of Java online submissions for Word Break. //Memory Usage: 39.7 MB, less than 10.64% of Java online submissions for Word Break. public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); boolean[] rst = new boolean[s.length() + 1]; rst[0] = true; for (int i = 1; i <= s.length(); i++) { for (int k = 0; k < i; k++) { if (rst[k] && dict.contains(s.substring(k, i))) { rst[i] = true; break; } } } return rst[s.length()]; }

解2

思路和解1一样，换一种字典搜索方式，效率提高一些。

// Runtime: 3 ms, faster than 84.19% of Java online submissions for Word Break. //Memory Usage: 37.2 MB, less than 10.64% of Java online submissions for Word Break. public boolean wordBreak(String s, List<String> wordDict) { Map<Integer, List<String>> sizedWordDict = new HashMap<>(); for (String word : wordDict) { List<String> words = sizedWordDict.computeIfAbsent(word.length(), k -> new ArrayList<>()); words.add(word); } boolean[] rst = new boolean[s.length() + 1]; rst[0] = true; for (int i = 1; i <= s.length(); i++) { for (int k = 0; k < i; k++) { if (rst[k]) { List<String> words = sizedWordDict.get(i - k); if (words != null && words.contains(s.substring(k, i))) { rst[i] = true; break; } } } } return rst[s.length()]; }