Leetcode discuss: 472. Concatenated Words

 Here is the discussion post. 

C# break into hashSet + DP problem

Oct. 20, 2020
472. Concatenated Words
Introduction
It is a hard level algorithm. I like to practice and also like to simplify the practice with an easy solution.

Case study
I like to choose one of Leetcode discussion posts to study, and write a simple test case. My goal is to write code to make this case work.

Assuming that words are the following three words:
{"cat","dog","catdog"}, my task is to prove that "catdog" can be break into "cat" and "dog". I also like to using dynamic programming solution to solve it.

catdog
012345
Declare dp array with size 7, dp[7] since "catdog"'s length is 6.
dp[6] = true, in other words, "catdog" is in original hashSet.
dp[3] is true since "dog" is in hashSet and dp[6] is true;
dp[0] is true since "cat" is in hashSet and dp[3] is true.

I am not sure how this dynamic programming is designed orginally. I just quickly studied and will come back with more ideas to write down.

Time complexity
Will be added very soon.

Advice
Plan to review 139 Word break I and 140 Word break II.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _472_ConcatenatedWords
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// Leetcode 472 - 
        /// Review my own practice first
        /// 139 Word break I
        /// 140 Word break II
        /// And then work on Leetcode 472 - Concatenated words
        /// study code
        /// https://leetcode.com/problems/concatenated-words/discuss/347648/C-HashSet-%2B-WordBreak
        /// </summary>
        /// <param name="words"></param>
        /// <returns></returns>
        public IList<string> FindAllConcatenatedWordsInADict(string[] words)
        {
            var result = new List<string>();
            if (words.Length <= 2)
            {
                return result;
            }

            var hashSet = new HashSet<string>(words);
            foreach (var word in words)
            {
                if (word == "")
                {
                    continue;
                }

                hashSet.Remove(word);

                var canBreak = WordBreak(word, hashSet);

                if (canBreak)
                {
                    result.Add(word);
                }

                hashSet.Add(word);
            }

            return result;
        }

        /// <summary>
        /// case study: 
        /// hashSet = {"cat","dog","catdog"} - remove catdog from hashSet before calling
        /// s = "catdog"
        /// dp = new bool[7];
        /// dp[6] = true; // "catdog" is in hashSet
        /// index = 3, s.Substring(3) is "dog" which is in hashSet. 
        /// dp[6] == true, s.Substring(3, 3) == "dog", j == 5
        /// so dp[3] = true
        /// likewise dp[0] = true since dp[3] = true, and s.Substring(0,3) = "cat", and "cat" is 
        /// hashSet.
        /// </summary>
        /// <param name="s"></param>
        /// <param name="hashSet"></param>
        /// <returns></returns>
        private bool WordBreak(string s, HashSet<string> hashSet)
        {
            if (s.Length == 0)
            {
                return false;
            }

            var n = s.Length;
            var dp = new bool[n + 1];
            dp[n] = true;

            for (int i = n - 1; i >= 0; --i)
            {
                for (int j = i; j < n; ++j)
                {
                    if (dp[j + 1] && hashSet.Contains(s.Substring(i, j - i + 1)))
                    {
                        dp[i] = true;
                        break;
                    }
                }
            }

            return dp[0];
        }
    }
}