Update Readme.md

wisdompeak · web-flow · commit f35b925d9002 · 2021-04-21T01:35:07.000-07:00
diff --git a/Trie/139.Word-Break/Readme.md b/Trie/139.Word-Break/Readme.md
@@ -1,12 +1,16 @@
 ### 139.Word-Break
 
-&#27492;&#39064;&#21482;&#35201;&#33021;&#24819;&#21040;&#29992;DP&#26469;&#20570;,&#23601;&#26159;&#25104;&#21151;&#30340;&#20851;&#38190;.
+#### &#35299;&#27861;1&#65306; DP
 
-&#26412;&#39064;&#21644;```322.Coin Change```&#24456;&#30456;&#20284;.&#35201;&#20351;&#24471;dp[i]&#33021;&#22815;&#25104;&#21151;,&#24517;&#28982;&#26159;&#38656;&#35201;&#25214;&#21040;&#19968;&#20010;&#23567;&#20110;i&#30340;&#24207;&#21495;j,&#20351;&#24471;s[j:i]&#24688;&#26159;&#19968;&#20010;&#21333;&#35789;,&#24182;&#19988;dp[j-1]&#20063;&#33021;&#25104;&#21151;.&#25152;&#20197;&#36941;&#21382;&#19968;&#19979;j&#21363;&#21487;.&#20110;&#26159;&#21160;&#24577;&#36716;&#31227;&#26041;&#31243;&#23601;&#20889;&#20986;&#26469;&#20102;,&#26102;&#38388;&#22797;&#26434;&#24230;&#26159;o(n^2).
+&#26412;&#39064;&#21644;```322.Coin Change```&#24456;&#30456;&#20284;&#65292;&#20196;dp[i]&#34920;&#31034;&#21069;i&#20010;&#23383;&#31526;&#26159;&#21542;&#33021;&#22815;break&#25104;&#21151;&#12290;&#36716;&#31227;&#26041;&#27861;&#26159;&#25214;&#21040;&#19968;&#20010;&#23567;&#20110;i&#30340;&#24207;&#21495;j,&#20351;&#24471;s[j:i]&#24688;&#26159;&#19968;&#20010;&#21333;&#35789;&#65292;&#24182;&#19988;dp[j-1]&#20063;&#33021;&#25104;&#21151;&#12290;&#25152;&#20197;&#36941;&#21382;&#19968;&#19979;j&#21363;&#21487;&#12290;
 
 &#21021;&#22987;&#26465;&#20214;&#38656;&#35201;&#31245;&#24494;&#27880;&#24847;&#19968;&#19979;.&#27492;&#39064;&#37324;,&#25913;&#25104;1-index&#26356;&#21152;&#26041;&#20415;,&#36825;&#26679;&#21021;&#22987;&#26465;&#20214;&#23601;&#26159;dp[0]&#38656;&#35201;&#35774;&#32622;&#20026;True&#21363;&#21487;.
 
 &#34917;&#20805;&#65306;&#30456;&#27604;&#20110;&#22312;&#20869;&#23618;&#24490;&#29615;&#20013;&#36941;&#21382;j&#30340;&#20301;&#32622;&#65292;&#26377;&#19968;&#31181;&#26356;&#39640;&#25928;&#30340;&#26041;&#27861;&#12290;&#23601;&#26159;&#22312;&#20869;&#23384;&#24490;&#29615;&#20013;&#36941;&#21382;wordDict&#65292;&#26597;&#30475;&#26159;&#21542;&#26377;&#20219;&#20309;&#19968;&#20010;&#21333;&#35789;word&#33021;&#22815;&#21305;&#37197;s[0:i]&#30340;&#21518;&#32512;&#12290;&#36825;&#31181;&#35299;&#27861;&#22312;s&#24456;&#38271;&#32780;wordDict&#24456;&#23567;&#30340;&#24773;&#20917;&#19979;&#65292;&#20248;&#21183;&#38750;&#24120;&#26126;&#26174;&#12290;
 
+#### &#35299;&#27861;2&#65306;DFS+Trie
+&#25105;&#20204;&#23558;&#25152;&#26377;&#30340;&#21333;&#35789;&#26500;&#24314;&#19968;&#26869;&#23383;&#20856;&#26641;&#12290;&#25105;&#20204;&#20174;&#21069;&#24448;&#21518;&#36941;&#21382;&#23383;&#31526;&#20018;&#65292;&#22914;&#26524;&#21457;&#29616;&#23383;&#31526;&#20018;&#30340;&#26576;&#27573;&#21069;&#32512;[0:i]&#23545;&#24212;&#30528;Trie&#20013;&#30340;&#19968;&#20010;&#21333;&#35789;&#65292;&#37027;&#20040;&#25105;&#20204;&#23601;&#21487;&#20197;&#20174;&#23545;&#21069;&#32512;&#20043;&#21518;&#30340;&#23376;&#20018;[i+1:n-1]&#36827;&#34892;&#36882;&#24402;&#22788;&#29702;&#12290;&#30452;&#33267;&#21457;&#29616;&#24688;&#22909;&#36882;&#24402;&#21040;&#23383;&#31526;&#20018;&#23614;&#37096;&#12290;
 
-[Leetcode Link](https://leetcode.com/problems/word-break)
+&#27880;&#24847;DFS&#35201;&#37197;&#21512;&#35760;&#24518;&#21270;&#20351;&#29992;&#65292;&#29992;memo[i]&#26469;&#26631;&#35760;[i:n-1]&#26159;&#21542;&#33021;&#22815;&#24050;&#32463;&#22833;&#36133;&#36807;&#12290;
+
+[Leetcode Link](https://leetcode.com/problems/word-break)

-Original file line number
+Diff line change
@@ @@ -1,12 +1,16 @@ @@
 ### 139.Word-Break
 -此题只要能想到用DP来做,就是成功的关键.
 +#### 解法1： DP
 -本题和```322.Coin Change```很相似.要使得dp[i]能够成功,必然是需要找到一个小于i的序号j,使得s[j:i]恰是一个单词,并且dp[j-1]也能成功.所以遍历一下j即可.于是动态转移方程就写出来了,时间复杂度是o(n^2).
 +本题和```322.Coin Change```很相似，令dp[i]表示前i个字符是否能够break成功。转移方法是找到一个小于i的序号j,使得s[j:i]恰是一个单词，并且dp[j-1]也能成功。所以遍历一下j即可。
 初始条件需要稍微注意一下.此题里,改成1-index更加方便,这样初始条件就是dp[0]需要设置为True即可.
 补充：相比于在内层循环中遍历j的位置，有一种更高效的方法。就是在内存循环中遍历wordDict，查看是否有任何一个单词word能够匹配s[0:i]的后缀。这种解法在s很长而wordDict很小的情况下，优势非常明显。
 +#### 解法2：DFS+Trie
 +我们将所有的单词构建一棵字典树。我们从前往后遍历字符串，如果发现字符串的某段前缀[0:i]对应着Trie中的一个单词，那么我们就可以从对前缀之后的子串[i+1:n-1]进行递归处理。直至发现恰好递归到字符串尾部。
 -[Leetcode Link](https://leetcode.com/problems/word-break)
 +注意DFS要配合记忆化使用，用memo[i]来标记[i:n-1]是否能够已经失败过。
++
 +[Leetcode Link](https://leetcode.com/problems/word-break)