Leetcode Problem 139 Word Break.txt

139. Word Break: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Language: C#

Hint to solve: Use dynamic programming.
Two pointers front(i) and back(j). Create a boolean array of size of string+1. 
From front pointer scan character by character back pointer and check if substring present in the dictionary. If yes then turn on flag for that index.
Repeat until you reach the end of the string. Check the flag array. If the final flag is turned ON that means that all the words were present in the dictionary.

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) 
    {
        bool[] characterFlag = new bool[s.Length+1];
        characterFlag[0] = true;
        
        int anyPreviousWordFound = 0;
        for(int i= 1; i<=s.Length; ++i)
        {
            for(int j = i-1; j>=0; --j)
            {
                if(characterFlag[j] == true)
                {
                    string sub = s.Substring(j,i-j);
                    //Console.WriteLine("j= "+j + " i= "+i + " sub: "+ sub);
                    string result = wordDict.FirstOrDefault(element => element == sub);
                    if(result != null)
                    {
                      characterFlag[i] = true;
                      //Console.WriteLine("Word found in dict setting index to true: "+i);
                      break;
                    }
                }
            }
        }
        return characterFlag[s.Length];
        
    }
}