#93 Leetcode Restore IP Addresses Solution in C, C++, Java, JavaScript, Python, C# Leetcode

#1 Code Example with C Programming

Code - C Programming

void gen_ip(const char *s, char *buff, int *seglen) {
    int i, j, k;
    for (i = 0; i  <  4; i ++) {
        strncpy(buff, s, seglen[i]);
        s += seglen[i];
        buff += seglen[i];
        *buff = '.';
        buff ++;
    }
    buff --;
    *buff = 0;
}
int validate(const char *s, int len) {
    int k = 0;
    
    if (len > 1 && *s == '0') return 0;
    
    while (len -- > 0) {
        k = k * 10 + *s - '0';
        s ++;
    }
    return k > 255 ? 0 : 1;
}
void bt(const char *s, char ***p, int *psz, int *pn, int total, int usedlen, int *seglen, int d) {
    int i, k;
    char buff[16];
    if (d == 4) {
        if (usedlen != total) return;
        gen_ip(s, buff, seglen);
        if (*psz == *pn) {
            *psz *= 2;
            *p = realloc(*p, *psz * sizeof(char *));
            //assert(*p);
        }
        (*p)[*pn] = malloc((total + 4) * sizeof(char));
        //assert((*p)[*pn]);
        strcpy((*p)[*pn], buff);
        (*pn) ++;
        return;
    }
    for (i = 1; i  < = 3; i ++) {
        if (validate(&s[usedlen], i)) {
            seglen[d] = i;
            bt(s, p, psz, pn, total, usedlen + i, seglen, d + 1);
        }
    }
}
char** restoreIpAddresses(char* s, int* returnSize) {
    char **p;
    int psz, pn;
    
    int seglen[4] = { 0 };
    
    pn = 0;
    psz = 10;
    p = malloc(psz * sizeof(char *));
    //assert(p);
    
    bt(s, &p, &psz, &pn, strlen(s), 0, seglen, 0);
    
    *returnSize = pn;
    
    return p;
}

Input

Output

#2 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
  public:
    vector < string> restoreIpAddresses(string s) {
        vector<string> temp;
        vector<string> ans;

        dfs(s, temp, ans);

        return ans;
    }

    void dfs(string s, vector < string> &temp, vector<string> &ans) {
        if (temp.size() == 4 && s.length() == 0) {
            ans.push_back(temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3]);
            return;
        }
        else if (temp.size() >= 4) {
            return;
        }

        for(int i = 1; i  < = 3 && i <= s.length(); i++) {
            string t = s.substr(0, i);
            if (t.length() > 1 && t[0] == '0') break;
            if (stoi(t) > 255) break;
            temp.push_back(t);
            dfs(s.substr(i, s.length() - i), temp, ans);
            temp.pop_back();
        }
    }
};

int main() {
    string str = "010010";
    Solution s;
    vector < string> ret = s.restoreIpAddresses(str);

    for (int i = 0; i  <  ret.size(); i++) {
        cout << ret[i] << endl;
    }
    return 0;
}

Input

Output

#3 Code Example with Java Programming

Code - Java Programming

class Solution {
  public List restoreIpAddresses(String s) {
    int n = s.length();
    LinkedList < String> segments = new LinkedList();
    List output = new ArrayList();
    backtrack(s, -1, 3, output, segments, n);
    return output;
  }
  
  private void backtrack(String s, int prevPos, int dots, List < String> output, LinkedList segments, int n) {
    int maxPos = Math.min(n - 1, prevPos + 4);
    for (int i = prevPos + 1; i  <  maxPos; i++) {
      String segment = s.substring(prevPos + 1, i + 1);
      if (isValid(segment)) {
        segments.add(segment);
        if (dots - 1 == 0) {
          updateOutput(s, i, n, segments, output);
        }
        else {
          backtrack(s, i, dots - 1, output, segments, n);
        }
        segments.removeLast();
      }
    }
  }
  
  public void updateOutput(String s, int currPos, int n, LinkedList < String> segments, List output) {
    String segment = s.substring(currPos + 1, n);
    if (isValid(segment)) {
      segments.add(segment);
      output.add(String.join(".", segments));
      segments.removeLast();
    }
  }

  public boolean isValid(String segment) {
    int m = segment.length();
    if (m > 3)
      return false;
    return (segment.charAt(0) != '0') ? (Integer.parseInt(segment)  < = 255) : (m == 1);
  }
}

Input

Output

#4 Code Example with Javascript Programming

Code - Javascript Programming

const restoreIpAddresses = function(s) {
  if (s.length < 4 || s.length > 12) return [];
  const res = [];
  let ans = "";
  for (let a = 1; a  < = 3; a++) {
    for (let b = 1; b  < = 3; b++) {
      for (let c = 1; c  < = 3; c++) {
        for (let d = 1; d  < = 3; d++) {
          if (a + b + c + d === s.length) {
            let A = +s.substr(0, a);
            let B = +s.substr(a, b);
            let C = +s.substr(a + b, c);
            let D = +s.substr(a + b + c, d);
            if (A  < = 255 && B <= 255 && C <= 255 && D <= 255) {
              if (
                ((ans = A + "." + B + "." + C + "." + D).length === s.length + 3)
              ) {
                res.push(ans);
              }
            }
          }
        }
      }
    }
  }
  return res;
};

Input

Output

#5 Code Example with Python Programming

Code - Python Programming

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) > 12: return []
        bfs = [(0, '')]
        for c in s:
            new = []
            c = int(c)
            for cur, st in bfs:
                if cur * 10 + c <= 255 and (st[-1:] != '0' or cur):
                    new.append((cur * 10 + c, st + str(c)))
                if st:
                    new.append((c, st + '.' + str(c)))
            bfs = new
        return [st for cur, st in bfs if st.count('.') == 3]

Input

#6 Code Example with C# Programming

Code - C# Programming

using System.Collections.Generic;

namespace LeetCode
{

    public class _093_RestoreIPAddresses
    {
        public IList < string> RestoreIpAddresses(string s)
        {
            var results = new List();
            RestoreIpAddresses(s, 0, "", 0, results);
            return results;
        }

        private void RestoreIpAddresses(string s, int startIndex, string existedString, int depth, List < string> results)
        {
            if (startIndex == s.Length && depth == 4)
            {
                results.Add(existedString);
                return;
            }
            if (startIndex == s.Length || depth == 4) { return; }

            for (int i = 1; i  <  4; i++)
            {
                if ((startIndex + i > s.Length) || (i == 2 && s[startIndex] == '0'))
                    break;
                if (i == 3)
                {
                    var num = int.Parse(s.Substring(startIndex, i));
                    if (num > 255)
                        break;
                }

                var newString = string.IsNullOrWhiteSpace(existedString)
                    ? s.Substring(startIndex, i)
                    : string.Join(".", existedString, s.Substring(startIndex, i));
                RestoreIpAddresses(s, startIndex + i, newString, depth + 1, results);
            }
        }
    }
}

Input

Output