cansplit_review.cs

/*"""
Given a string s and a list of words w, determine if s can be split into a space-separated sequence of one or more words in w.

For example, given
s = "catdog"
w = ["dog", "car", "catch", "cat", "tiger", "at"]
==> True

s = "catdogtail"
w = ["dog", "car", "catch", "cat", "tiger", "at"]
==> False

s = "catdogtail"
w = ["dog", "car", "catch", "tail", "cat", "tiger", "at"]
==> True

Return true because "catdog" can be segmented as "cat", "dog", and both of them are in dict.

"""

"catcat"
["cat"]


// for every word in w
//    if word is in s
//      remove word from s

"acatdog"
["cat" "adog"]
"adog"

"cat2dog"
c
ca
cat -> 2dog
cat2 -> dog
["cat", "cat2", "dog"]
*/

using System.Collections.Generic;
using System.Text;

class Solution
{
    public static void Main()
    {
        TestCanSplit();
    }
    
    public bool CanSplit(string s, string[] w) //cat2dog
    {
        var set = new HashSet<string>(w); // cat, cat2, dog
        var buffer = new StringBuilder();
        
        for (int i = 0; i < s.Length; i++)
        {
            var current = s[i]; // 
            buffer.Append(current); //
            var res = buffer.ToString(); //dog
            
            if (set.Contains(res))
            {
                var substring = s.Substring(i + 1, s.Length - i - 1);
                System.Console.WriteLine(substring);
                if (substring.Length == 0)
                    return true;
                if (CanSplit(substring, w))
                    return true;
            }
        }
        
        return false;
    }
    
    public static void TestCanSplit()
    {
        var s = "cat2dog";
        var w = new[] { "cat", "cat2", "dog" };
        
        var result = new Solution().CanSplit(s, w);
        
        System.Console.WriteLine(result);
    }
}