Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created June 23, 2016 01:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jianminchen/bd9301c3ad38d801001d1d66a08256fe to your computer and use it in GitHub Desktop.
Leetcode 139 - word break - write a test case to understand the process of Dynamic programming method
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