Word Break (M)
題目
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
題意
判斷給定字串按照某種方式分割后得到的所有子串能否在給定陣列中找到，
思路
-
純DFS會超時，所以利用Map記錄下所有執行過的遞回的結果，
-
動態規劃，dp[i]代表s中以第i個字符結尾的子串是否滿足要求，則狀態轉移方程為：只要有任意一個j(j<i)滿足 dp[j]==true && wordDict.contains(s.substring(j,i))==true，那么dp[i]=true，
代碼實作
Java
記憶化搜索
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return isValid(s, 0, wordDict, new HashMap<>());
}
private boolean isValid(String s, int start, List<String> wordDict, Map<Integer, Boolean> record) {
if (start == s.length()) {
return true;
}
if (record.containsKey(start)) {
return record.get(start);
}
for (int end = start + 1; end <= s.length(); end++) {
if (wordDict.contains(s.substring(start, end)) && isValid(s, end, wordDict, record)) {
record.put(start, true);
return true;
}
}
record.put(start, false);
return false;
}
}
動態規劃
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
JavaScript
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
let dp = new Array(s.length + 1).fill(false)
dp[0] = true
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordDict.indexOf(s.slice(j, i)) >= 0) {
dp[i] = true
break
}
}
}
return dp[s.length]
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139173.html
標籤：其他
上一篇：排序二叉樹和平衡二叉樹