139. Word Break

Here is my post on Leetcode.com. I learn that it is important for me to write something to share my practice.

Here is the copy of transcript of the post:

It is time for me to review the algorithm in July 2019. My first practice was in 2016.

Case study

I like to do a quick case study how to approach the algorithm using dynamic programming.
s="leetcode", wordDict = ["leet","code"].

dp = new bool[9]
empty string: "", return true; dp[0] = true
dp[1], "l", break into all possible suffix string, ""+"l", but "l" is not in dictionary. dp[1] = false;
dp[2],"le", work on "e", "le", both fails, dp[2] = false;
dp[3], "lee", work on "e","ee","lee", all of three fails, dp[3] = false;
dp[4], "leet", work on "e","ee","lee","leet", last one success, fp[4] = true;
...

Here are highlights:

1. It can be solved using dynamic programming solution with bottom up approach;
2. Search every possible suffix string from longest one to smallest on to see if it is in the word dictionary, and subproblem return true or not;
3. The code is not readable. Need to remove unused variable left, and also write very meaningful comment.

public class Solution {
    public bool WordBreak(string s, ISet<string> wordDict) {
         if (s == null || s.Length == 0)
                return false;

            int len = s.Length;

            bool[] cache = new bool[len + 1];
            cache[0] = true; // "" empty string 
           
            for (int i = 0; i < len; i++)
            {
                // "ab", "abc"
                // "a"
                // right string start position point index 
                for (int pos = i; pos >= 0; pos--)
                {
                    string left  = pos == 0 ? "" : s.Substring(0, pos);
                    //string right = s.Substring(pos, len - left.Length);   // bug001 - not len, should be i
                    string right = s.Substring(pos, i + 1 - left.Length);

                    if(cache[pos] && wordDict.Contains(right))
                    {
                        cache[i + 1] = true;
                        break;
                    }
                }
                
            }

            return cache[len]; 
    }
}