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

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict)
        {
            int len = s.Length;
            int[,] T = new int[len, len];
            wordDict = wordDict.OrderBy(q => q).ToList();


            for (int i = 0; i < len; i++)
            {
                for (int j = 0; j < len; j++)
                {
                    T[i,j] = -1; //-1 indicates string between i to j cannot be split
                }
            }
            //fill up the matrix in bottom up manner
            for (int l = 1; l <= len; l++)
            {
                for (int i = 0; i < len - l + 1; i++)
                {
                    int j =  l+i-1;
                    string sub = s.Substring(i, l);
                    //if string between i to j is in dictionary T[i][j] is true
                    if ((wordDict as List<string>).BinarySearch(sub) >= 0)
                    {
                        T[i, j] = i;
                    }
                    
                    //find a k between i+1 to j such that T[i][k-1] && T[k][j] are both true 
                    for (int k = i + 1; k <= j; k++)
                    {
                        if (T[i, k - 1] != -1 && T[k,j] != -1)
                        {
                            T[i, j] = k;
                            break;
                        }
                    }
                }
            }
            if (T[0, len - 1] == -1)
            {
                return false;
            }


            return true;
        }
}

unit test:
using Xunit;
using LeetCode._100LikedQuestion.Medium;
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace LeetCode._100LikedQuestion.Medium.Tests
{
    public class WordBreakSoluTests
    {
        WordBreakSolu _wordBreakSolu;
        public WordBreakSoluTests()
        {
            _wordBreakSolu = new WordBreakSolu();
        }
       

        [Theory]
        [ClassData(typeof(CalculatorTestData))]
        public void RunTest(string s, List<string> wordDict, bool result)
        {
           var resu = _wordBreakSolu.WordBreak(s,wordDict);
            Assert.Equal(resu, result);
        }
    }

    public class CalculatorTestData : IEnumerable<object[]>
    {
        public IEnumerator<object[]> GetEnumerator()
        {
            
            yield return new object[] { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", new List<string> { "a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa" }, false };
            yield return new object[] { "applepenapple", new List<string> { "apple", "pen" }, true };
            yield return new object[] { "aaaaaaa", new List<string> { "aaaa", "aaa" }, true };
            yield return new object[] { "leetcode", new List<string> { "leet", "code" }, true };
            yield return new object[] { "catsandog", new List<string> { "cats", "dog", "sand", "and", "cat" }, false };
        }

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    }
}

Array C# dataStructure design Dispose dotnet Indexes LINUX MongoDB multithreadedapp OOM PerformanceGain Task thread