C# beats 90% without DFS


  • 0
    T
    public IList<string> RestoreIpAddresses(string s) {
                List<string> res = new List<string>();
                if (s.Length < 4 || s.Length > 12)
                    return res;
                int n = s.Length;
                List<List<int>> iL = new List<List<int>>();
                for (int i1 = 1; i1 < 4; i1++)
                    for (int i2 = 1; i2 < 4; i2++)
                        for (int i3 = 1; i3 < 4; i3++)
                            for (int i4 = 1; i4 < 4; i4++)
                                if (i1 + i2 + i3 + i4 == n)
                                    iL.Add(new List<int> { i1, i2, i3, i4 });
                for (int k = 0; k < iL.Count; k++)
                {
                    int a = Convert.ToInt32(s.Substring(0, iL[k][0]));
                    int b = Convert.ToInt32(s.Substring(iL[k][0], iL[k][1]));
                    int c = Convert.ToInt32(s.Substring(iL[k][0] + iL[k][1], iL[k][2]));
                    int d = Convert.ToInt32(s.Substring(iL[k][0] + iL[k][1] + iL[k][2], iL[k][3]));
                    string sTemp = string.Format("{0}{1}{2}{3}", a, b, c, d);
                    if (a < 256 && b < 256 && c < 256 && d < 256 && sTemp == s)
                        res.Add(string.Format("{0}.{1}.{2}.{3}",a,b,c,d));
                }
                return res;
        }
    

Log in to reply
 

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