Created
June 23, 2016 01:04
Star
You must be signed in to star a gist
Leetcode 139 - word break - write a test case to understand the process of Dynamic programming method
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace _139WordBreak | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
// test case: | |
// s = "leetcode", | |
// dict = ["leet", "code"]. | |
string s = "abcd"; | |
string[] dict = new string[]{ | |
"a", "bc","d" | |
}; | |
bool result = wordBreak(s, new HashSet<string>(dict.ToList())); | |
} | |
/* | |
* Leetcode 139 Word Break | |
* | |
* | |
* source code from: | |
* http://bangbingsyb.blogspot.ca/2014/11/leetcode-word-break-i-ii.html | |
* | |
* Try to analyze the problem. | |
* | |
* Use DFS to do search, but to avoid duplication in calculation, | |
* use an array dp to save S[0:i] - break or not | |
dp[i]:S[0:i-1] breakable or not。 | |
for example, dp[1] - s[0] is breakable or not. | |
* | |
dp[0] = true | |
dp[i] = true if and only if: | |
1. there is one i-1 >= k >= 0,s[k:i-1] is in the dict。 | |
2. s[0: k-1] is breakable,so dp[k] = true。 | |
* | |
* This practice is to work on test case: | |
* "abcd", | |
* string[] dict = new string[]{ | |
"a", "bc","d" | |
}; | |
* | |
* We have to prepare an array dp[] to calculate | |
* dp[i] value from 0 to 4. | |
* And then, we can determine if dp[4] is true not | |
* dp[0] = true; | |
* dp[1] = true, "a" can be constructed by dictionary | |
* dp[2] = false, "ab" cannot be constructed by dictionary | |
* dp[3] = true, "abc" can be constructed by dictionary "a"+"bc" | |
* dp[4] = true, "abcd" can be constructed by dictionary | |
* | |
* | |
* | |
*/ | |
public static bool wordBreak( | |
string s, | |
HashSet<string> dict) | |
{ | |
if (s == null || s.Length == 0) | |
return false; | |
int len = s.Length; | |
bool[] dp = new bool[len + 1]; | |
dp[0] = true; | |
for (int i = 0; i < len; i++) | |
{ | |
// For each string with length i - (0 to len-1) | |
// make judgement if it is construtable or not | |
// "a", "ab", "abc", "abcd" | |
// | |
// Look into two substrings: | |
// "ab" is not constructable | |
// "abc" is constructable "a" +"bc" | |
// exhaustive search three times: | |
// check dp check dictionary | |
// 1. "ab" "c" | |
// 2. "a" "bc" <- it is constructable, break the loop | |
// 3. "" "abc" | |
// s.Substring(0, j) - first j chars - check dp array directly | |
// s.Subsring(j, i-j+1) - rest of string - look up dictionary | |
for (int j = i; j >= 0; j--) | |
{ | |
//string firstRunner = s.Substring(0, j); | |
string secondRunner = s.Substring(j, i - j + 1); | |
// firstRunner should be true - in dictionary | |
// dp[j] | |
// j starts from i, i is from 0 to increment | |
// | |
if (dp[j] && dict.Contains(secondRunner)) | |
{ | |
dp[i + 1] = true; | |
break; | |
} | |
} | |
} | |
return dp[len]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment