Create 139.单词拆分(中等).md

JavaCodeMing · JavaCodeMing · commit a7012fedc2de · 2020-06-26T17:11:18.000+08:00
diff --git a/Algorithm/139.单词拆分(中等).md b/Algorithm/139.单词拆分(中等).md
@@ -0,0 +1,42 @@
+```text
+��Ŀ: ����һ���ǿ��ַ���s��һ�������ǿյ����б����ֵ�wordDict,�ж�s�Ƿ���Ա��ո���Ϊһ���������ֵ��г��ֵĵ���;
+    ˵��:
+        ���ʱ�����ظ�ʹ���ֵ��еĵ���
+        ���Լ����ֵ���û���ظ��ĵ���
+    ʾ�� 1: 
+        ����: s = "leetcode", wordDict = ["leet", "code"]
+        ���: true
+        ����: ���� true ��Ϊ "leetcode" ���Ա���ֳ� "leet code"
+1.��̬�滮:
+    [1]˼·:
+        (1)����dp[i]��ʾ�ַ���s��ǰi���ַ���ɵ��ַ���s[0..i?1]�Ƿ��ܲ�ֳ����ɸ��ֵ��г��ֵĵ���;
+        (2)�Էָ��j���ָ��ַ���s[0..i?1],����s[0..j-1],s[j..i?1]
+        (3)��dp[j]Ϊtrue(���ַ���s[0..j-1]�ܲ�ֳ����ɸ��ֵ��г��ֵĵ���),���ַ���s[j..i-1]���ֵ��г��ֵĵ���ʱ,dp[i]=true
+        (4)���Ͽɵ�ת�Ʒ���Ϊ: dp[i]=dp[j] && check(s[j..i?1]) (check(s[j..i?1])��ʾ�Ӵ�s[j..i-1]s[j..i?1]�Ƿ�������ֵ���)
+    [2]ʵ��:
+        class Solution {
+            public boolean wordBreak(String s, List<String> wordDict) {
+                // ʹ���ֵ伯�Ϲ�����ϣ��
+                Set<String> wordDictSet = new HashSet<>(wordDict);
+                // ����dp[i]
+                boolean[] dp = new boolean[s.length()+1];
+                // ���ӱ߽�����(�±�Ϊ0֮ǰ���ַ���Ҳ��Ϊ�մ�)
+                dp[0] = true;
+                //����
+                for (int i = 1; i <= s.length(); i++) {
+                    for (int j = 0; j < i; j++) {
+                        // ת�Ʒ���
+                        if(dp[j] && wordDictSet.contains(s.substring(j,i))){
+                            dp[i] = true;
+                            break;
+                        }
+                    }
+                }
+                // dp[s.length()]��ʾ���������ַ���s[0..s.length()]�Ƿ��ܲ�ֳ����ɸ��ֵ��г��ֵĵ���
+                return dp[s.length()];
+            }
+        }
+    [3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�: O(N^2),NΪ�ַ����ĳ���
+        (2)�ռ临�Ӷ�: O(N),NΪ�ַ����ĳ���,dp�����Լ���ϣ������ҪO(n)�Ŀռ临�Ӷ�
+```

-Original file line number
+Diff line change
@@ @@ -0,0 +1,42 @@ @@
 +```text
 +题目: 给定一个非空字符串s和一个包含非空单词列表的字典wordDict,判定s是否可以被空格拆分为一个或多个在字典中出现的单词;
 +    说明:
 +        拆分时可以重复使用字典中的单词
 +        可以假设字典中没有重复的单词
 +    示例 1:
 +        输入: s = "leetcode", wordDict = ["leet", "code"]
 +        输出: true
 +        解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"
 +1.动态规划:
 +    [1]思路:
 +        (1)定义dp[i]表示字符串s的前i个字符组成的字符串s[0..i?1]是否能拆分成若干个字典中出现的单词;
 +        (2)以分割点j来分割字符串s[0..i?1],即得s[0..j-1],s[j..i?1]
 +        (3)则当dp[j]为true(即字符串s[0..j-1]能拆分成若干个字典中出现的单词),且字符串s[j..i-1]是字典中出现的单词时,dp[i]=true
 +        (4)由上可得转移方程为: dp[i]=dp[j] && check(s[j..i?1]) (check(s[j..i?1])表示子串s[j..i-1]s[j..i?1]是否出现在字典中)
 +    [2]实现:
 +        class Solution {
 +            public boolean wordBreak(String s, List<String> wordDict) {
 +                // 使用字典集合构建哈希表
 +                Set<String> wordDictSet = new HashSet<>(wordDict);
 +                // 创建dp[i]
 +                boolean[] dp = new boolean[s.length()+1];
 +                // 添加边界条件(下标为0之前的字符串也即为空串)
 +                dp[0] = true;
 +                //遍历
 +                for (int i = 1; i <= s.length(); i++) {
 +                    for (int j = 0; j < i; j++) {
 +                        // 转移方程
 +                        if(dp[j] && wordDictSet.contains(s.substring(j,i))){
 +                            dp[i] = true;
 +                            break;
 +                        }
 +                    }
 +                }
 +                // dp[s.length()]表示的是整个字符串s[0..s.length()]是否能拆分成若干个字典中出现的单词
 +                return dp[s.length()];
 +            }
 +        }
 +    [3]复杂度分析:
 +        (1)时间复杂度: O(N^2),N为字符串的长度
 +        (2)空间复杂度: O(N),N为字符串的长度,dp数组以及哈希表各需要O(n)的空间复杂度
 +```