一、題目描述
給你一個字符串?s?和一個字符串列表?wordDict?作為字典。如果可以利用字典中出現的一個或多個單詞拼接出?s?則返回?true。
注意：不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"] 輸出: true 解釋: 返回 true 因為 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"] 輸出: true 解釋: 返回 true 因為 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重復使用字典中的單詞。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 輸出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s?和?wordDict[i]?僅由小寫英文字母組成wordDict?中的所有字符串?互不相同
二、解題思路
1. 初始化動態規劃數組：
- 創建一個布爾數組?
dp，長度為?s.length() + 1。 - 將?
dp[0]?設置為?true，因為空字符串可以被看作是由空單詞列表拼接而成。
2. 填充動態規劃數組：
- 遍歷字符串?
s?的每個可能的結束位置?i，從?1?到?s.length()。 - 對于每個?
i，再進行一次內部循環，遍歷所有可能的前一個位置?j，從?0?到?i-1。 - 在內部循環中，檢查?
dp[j]?是否為?true，且?s.substring(j, i)?是否在字典?wordDict?中。 - 如果上述條件成立，說明從?
j?到?i?的子串可以被字典中的單詞拼接而成，因此將?dp[i]?設置為?true。
3. 返回結果：
- 動態規劃數組填充完畢后，
dp[s.length()]?的值即為所求，它表示整個字符串?s?是否可以被字典中的單詞拼接而成。 - 返回?
dp[s.length()]?作為函數的輸出。
這個動態規劃解法的核心思想是將大問題分解為小問題，通過檢查所有可能的前綴來逐步構建出整個字符串是否可以被拼接的答案。
三、具體代碼
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordSet = new HashSet<>(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] && wordSet.contains(s.substring(j, i))) {dp[i] = true;break;}}}return dp[s.length()];}
}
四、時間復雜度和空間復雜度
1. 時間復雜度
- 將列表?
wordDict?轉換為哈希集合?wordSet?的時間復雜度是 O(k)，其中 k 是字典中單詞的數量。這是因為需要對每個單詞進行哈希運算。 - 初始化布爾數組?
dp?的時間復雜度是 O(n)，其中 n 是字符串?s?的長度。 - 雙層循環的時間復雜度是 O(n^2)，因為外層循環執行了 n 次，內層循環在最壞情況下也可能執行 n 次。
substring?操作的時間復雜度是 O(k)，其中 k 是子字符串的長度。在最壞情況下，k 可以達到 n，但通常情況下，k 會有一個上限，即字典中最長單詞的長度。
綜上所述，總的時間復雜度是 O(n^2 * m)，其中 m 是字典中單詞的平均長度。這是因為對于每個子字符串，我們需要檢查它是否在字典中，這個操作的時間復雜度是 O(m)。
2. 空間復雜度
- 哈希集合?
wordSet?的空間復雜度是 O(k)，其中 k 是字典中單詞的數量。 - 布爾數組?
dp?的空間復雜度是 O(n)，其中 n 是字符串?s?的長度。
因此，總的空間復雜度是 O(n + k)，即由動態規劃數組和哈希集合構成的空間需求。
五、總結知識點
-
動態規劃：這是一種算法設計技術，用于解決優化問題。它將問題分解為更小的子問題，并通過組合子問題的解來解決原始問題。在這個問題中，
dp?數組用于存儲子問題的解，即字符串的前綴是否可以被字典中的單詞拼接而成。 -
哈希集合：
HashSet?是 Java 中的一個集合實現，用于存儲不重復的元素，并且可以快速判斷一個元素是否存在于集合中。在這個問題中，wordSet?用于存儲字典中的單詞，以便快速檢查一個子字符串是否是字典中的單詞。 -
字符串操作：
substring?方法是 Java?String?類的一個方法，用于提取字符串中的一個子串。在這個問題中，它用于提取從位置?j?到?i?的子字符串，檢查它是否在字典中。 -
數組的初始化：代碼中使用?
new boolean[s.length() + 1]?初始化了一個布爾數組?dp，所有元素默認為?false。然后，dp[0]?被顯式設置為?true，因為空字符串可以被看作是由空單詞列表拼接而成。 -
雙層循環：外層循環遍歷字符串?
s?的每個可能的結束位置?i，內層循環遍歷所有可能的前一個位置?j。這種結構用于填充動態規劃數組?dp。 -
遞推關系：動態規劃的核心是找到子問題之間的遞推關系。在這個問題中，
dp[i]?的值取決于?dp[j]（j < i）的值和子字符串?s.substring(j, i)?是否在字典中。 -
邊界條件：在動態規劃中，通常需要設置邊界條件。在這個問題中，
dp[0]?被設置為?true，這是遞推的起始條件。
以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。
】)
上)
