[Uber][LeetCode] Word Break

Problem: Given a non-empty string and a dictionary containing a list of non-empty words, determine if given string can be segmented into a space-separated sequence of one or more dictionary words. 

Example:

Input: s = "Iamace", wordDict = ["I", "a", "am" "ace"]
Output: true
Explanation: Return true because "Iamace" can be segmented as "I am ace".

Approach: The immediate approach which comes to mind is DP with a 2D table where its element T[i][j] tells if sub string [i...j] can be partitioned into dictionary words or not. Obviously T[0][n-1] will be our answer. Table T can be filled in following way -

FOREACH length = 1 to string.Length:

FOREACH i = 0 to i = string.Length - length

• If S[i...i + length - 1] is a dictionary word then T[i][i + length - 1] = true.
• ELSE 
• FOREACH j = i to i + length - 2 // checking for each partition
• IF T[i][j] && T[j+1][i + length -1] is true then T[i][i + length - 1] = true // Got a partition
• T[i][i + length - 1] = false

Now this solution will work fine and is obviously is way better than the brute force approach but still its time complexity is O(n^3) ignoring the string comparison and finding word in dictionary with O (n^2) space complexity. 

Can we do better? Let's see it closely. There are following points to be considered -

1. We always need to check S[0...i] as we want result from the first character only.
2. Do we need to look at each index? I think not, we just need to consider indexes which tells us that from 0...index, you can partition the string into valid words i.e. sub-string S[0...i] can be partitioned into dictionary words so now we just need to check whether sub-string S[i+1... S.Length - 1]  can be partitioned into dictionary words or not.
3. Considering above 2 points, we can see that we don't need 2D table to store data. We can just have 1D array T where T[i] is true if S[0...i] can be broken into dictionary words. Right? It looks correct but if we see, we just need the end index result i.e. T[S.Length -1] that means we can ignore the other values in T. It tells us we can use a bool variable which can tell us result at current index and we can return it.

Implementation in C#:

        public static bool WordBreak1(string s, IList<string> wordDict)

        {

            List<int> validIndexes = new List<int>();

            validIndexes.Add(-1);

            bool isValidonCurrentIndex = false;

            for (int i = 0; i < s.Length; ++i)

            {

                isValidonCurrentIndex = false;

                for (int j = validIndexes.Count - 1; j >= 0; --j) // only check for valid indexes

                {

                    if (wordDict.Contains(s.Substring(validIndexes[j] + 1, i - validIndexes[j])))

                    {

                        isValidonCurrentIndex = true;

                        validIndexes.Add(i);

                        break;

                    }

                }

            }

            return isValidonCurrentIndex;

        }

Complexity: O(n^2)