C# - DP + Backtracking beat 92% submissions


  • 0
    N
    private int size = 0;
                public IList<string> WordBreak(string s, IList<string> wordDict)
                {
                    size = s.Length;
                    var hash = new HashSet<string>(wordDict);
                    var valid = new Dictionary<int, List<string>>();
                    var result = new List<string>();
                    WordBreakImpl(s, hash, valid, result, new LinkedList<string>());
                    return result;
                }
    
                public bool WordBreakImpl(
                    string s,
                    HashSet<string> wordDict,
                    Dictionary<int, List<string>> valid,
                    List<string> result,
                    LinkedList<string> current)
                {
                    List<string> existing;
                    if (valid.TryGetValue(s.Length, out existing))
                    {
                        if (existing == null) return false; // no potential
                        foreach (var dp_str in existing)
                            result.Add(string.Join(" ", current) + " " + dp_str);
                        return true;
                    }
    
                    bool succeeded = false;
                    for (int i = 0; i < s.Length; i++)
                    {
                        var subStrLen = i + 1;
                        var subs = s.Substring(0, subStrLen);
    
                        if (!wordDict.Contains(subs)) continue;
                        if (valid.TryGetValue(s.Length - subStrLen, out existing) && existing == null) continue;
    
                        var node = current.AddLast(subs);
    
                        if (subStrLen == s.Length)
                        {
                            result.Add(string.Join(" ", current));
                            if (!valid.TryGetValue(s.Length, out existing))
                            {
                                existing = new List<string>();
                                valid.Add(s.Length, existing);
                            }
    
                            existing.Add(subs);
                            current.RemoveLast();
                            return true;
                        }
    
                        var rem = s.Substring(subStrLen);
                        if (WordBreakImpl(rem, wordDict, valid, result, current))
                        {
                            foreach (var list in valid[s.Length - subStrLen])
                            {
                                var str = string.Join(" ", list);
                                if (s.Length < size) // not the beginning
                                {
                                    if (!valid.TryGetValue(s.Length, out existing))
                                    {
                                        existing = new List<string>();
                                        valid.Add(s.Length, existing);
                                    }
    
                                    existing.Add(subs + " " + str);
                                }
                            }
    
                            succeeded = true;
                        }
                        else
                        {
                            valid.Add(s.Length - subStrLen, null);
                        }
    
                        current.RemoveLast(); // Backtrack
                    }
    
                    return succeeded;
                }
    

    Feedback/comments welcome!


Log in to reply
 

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