Leetcode discuss: 140. Word Break II

 Here is my discussion post. 

C# 2020 Oct 20 warmup practice using DFS + memoization

Oct. 20, 2020
140. Word Break II
Introduction
What is the best way to master a DFS + memoization algorithm? I like to take 30 minutes to warmup this hard level algorithm.

Case study
I do think that it is best investment of time to work on a simple test case, and then go over the detail how to solve the problem.
Given a string "catsanddog", and a dictionary with the following words:
{ "cat", "cats", "and", "sand", "dog" }, find all possible word breaks.
There are two answers:
"cat sand dog" and "cats and dog".

Run depth first search, and also memoize the intermediate string with words to construct, here are hashMap with the following entries with the order:

1. key = "dog", value = "dog";
2. key = "sanddog", value = "sand dog";
3. key= "anddog", value = "and dog";
4. key = "catsanddog", value is list of two strings, "cat sand dog" and "cats and dog".

The hashMap is used once for string "dog" to look up, and return a linked list directly.

First, go over all the words one by one, first one is "cat", and then run depth first search, next one is "sand" and then "dog" is last, and "" is searched as base case.

C# LinkedList - IEnumerable
It is also the good practice to see how to write LinkedList based on interface IEnumerable.

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

namespace _140_word_break_II___Oct_20
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = "catsanddog";
            var wordDict = new string[] { "cat", "cats", "and", "sand", "dog" };

            var result = WordBreak(s, wordDict);

            /// cats and dog
            /// cat sand dog
            Debug.Assert(result[0].CompareTo("cat sand dog") == 0);
            Debug.Assert(result[1].CompareTo("cats and dog") == 0);
        }

        /// <summary>
        /// code review on Oct. 20, 2020
        /// </summary>
        /// <param name="s"></param>
        /// <param name="wordDict"></param>
        /// <returns></returns>
        public static IList<string> WordBreak(string s, IList<string> wordDict)
        {
            return runDFS(s, wordDict, new Dictionary<string, LinkedList<string>>());
        }
        
        /// <summary>
        /// "catsanddog"
        /// words = {"cat","cats","and","sand","dog"}
        /// cats and dog
        /// cat sand dog
        /// </summary>
        /// <param name="s"></param>
        /// <param name="wordDict"></param>
        /// <param name="map"></param>
        /// <returns></returns>
        private static IList<string> runDFS(string s, IList<string> wordDict, Dictionary<string, LinkedList<String>> map)
        {
            // Look up cache 
            if (map.ContainsKey(s))
            {
                return map[s].ToList();
            }

            var list = new LinkedList<String>();

            // base case 
            if (s.Length == 0)
            {
                list.AddLast("");
                return list.ToList();
            }

            // go over each word in dictionary
            foreach (string word in wordDict)
            {
                // C# string.StartsWith API
                if (s.StartsWith(word))
                {
                    var nextList = runDFS(s.Substring(word.Length), wordDict, map);

                    foreach (string sub in nextList)
                    {
                        list.AddLast(word + (string.IsNullOrEmpty(sub) ? "" : " ") + sub);
                    }
                }
            }

            // memoization
            map.Add(s, list);

            return list.ToList();
        }
    }
}