C# DFS Solution


  • 0
    K
    public class Solution {
        public IList<string> RestoreIpAddresses(string s) {
            IList<string> list = new List<string>();
            Helper(list, s, 0, new StringBuilder(), 0);
            return list;
        }
        
        private void Helper(IList<string> list, string s, int index, StringBuilder curr, int dots){
            if(dots == 4){
                if (index == s.Length) {
                    list.Add(curr.ToString(0, curr.Length - 1));
                }
                return;
            }
            
            if(index == s.Length){
                return;
            }
            
            curr.Append(s[index]);
            curr.Append(".");
            Helper(list, s, index + 1, curr, dots + 1);
            curr.Length -=2;
            
            if(index < s.Length - 1 && s[index] != '0') {
                curr.Append(s.Substring(index, 2));
                curr.Append(".");
                Helper(list, s, index + 2, curr, dots + 1);
                curr.Length -=3;
            }
            
            if(index < s.Length - 2) {
                int val = Convert.ToInt32(s.Substring(index, 3));
                if(val <= 255 & val >= 100){
                    curr.Append(s.Substring(index, 3));
                    curr.Append(".");
                    Helper(list, s, index + 3, curr, dots + 1);
                    curr.Length -= 4;
                }
            }        
        }
    }
    

Log in to reply
 

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