C# backtracking implementation


  • 0
    C

    C# backtracking implementation

            public  IList<string> RestoreIpAddresses(string s)
            {
                List<string> res = new List<string>();
                List<string> ips = new List<string>();
    
                Find(res, ips, s, 0);
                return res;
            }
    
            private void Find(IList<string> res, IList<string> ips, string s, int start)
            {
                if (ips.Count == 4 && start == s.Length)
                {
                    res.Add(string.Join(".", ips));
                    return;
                }
    
                if (s.Length - start > (4 - ips.Count) * 3) // pruning if right side contains more characters than needed
                {
                    return;
                }
    
                for (int i = start; i < start + 4 && i < s.Length; i++)
                {
                    string ip = s.Substring(start, i - start + 1);
                    if (int.Parse(ip) > 255 || int.Parse(ip).ToString() != ip) // prevent digit larger or starts with 0
                    {
                        return;
                    }
    
                    ips.Add(ip);
                    Find(res, ips, s, i + 1);
                    ips.RemoveAt(ips.Count - 1);
                }
            }
    

Log in to reply
 

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