C# DFS + Caching


  • 3
    public class Solution {
        Dictionary<string, List<string>> dp = new Dictionary<string, List<string>>();
    
        public IList<string> WordBreak(string s, ISet<string> wordDict)
        {
            return WordBreak(s, 0, s.Length - 1, wordDict);
        }
    
        public IList<string> WordBreak(string s, int start, int end, ISet<string> wordDict)
        {
            string key = start + "_" + end;
            if (dp.ContainsKey(key))
            {
                return dp[key];
            }
    
            List<string> sentences = new List<string>();
            for (int sub = start ; sub < end ; sub++)
            {
                int subLength = sub - start + 1;
                string subStr = s.Substring(start, subLength);
                if (wordDict.Contains(subStr))
                {
                    IList<string> rest = WordBreak(s, sub + 1, end, wordDict);
                    if (rest.Any())
                    {
                        sentences.AddRange(rest.Select(ss => subStr + " " + ss));
                    }
                }
            }
    
            string curSentence = s.Substring(start, end - start + 1);
            if (wordDict.Contains(curSentence))
            {
                sentences.Add(curSentence);
            }
    
            dp[key] = sentences;
            return sentences;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.