Skip to content

Instantly share code, notes, and snippets.

@run

run/Restore IP Addresses.cpp

Created October 28, 2014 02:50
Show Gist options
  • Save run/4cf29c42d427dd8e1588 to your computer and use it in GitHub Desktop.
Save run/4cf29c42d427dd8e1588 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Runzhen created this gist Oct 28, 2014.
    60 changes: 60 additions & 0 deletions Restore IP Addresses.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,60 @@
    class Solution {
    public:
    vector<string> restoreIpAddresses(string s) {
    vector<string> tmp;
    vector<string> result;

    if (s.size() < 4 && s.size() > 12) {
    return result;
    }

    dfs(0, 4, s, tmp, result);

    return result;
    }

    void dfs(int start, int count, string &s,
    vector<string> &tmp, vector<string> &result)
    {
    if (start == s.size() && count == 0) {
    string str = concatenate(tmp);
    result.push_back(str);

    return ;
    }

    for (int i = start; i < s.size(); i++) {
    if (true == check(s.substr(start, i-start+1))) {
    tmp.push_back(s.substr(start, i-start+1));
    dfs(i+1, count-1, s, tmp, result);
    tmp.pop_back();
    }
    }
    }

    string concatenate(vector<string> &tmp)
    {
    string str;
    int i;
    for (i = 0; i < tmp.size()-1; i++) {
    str += tmp[i];
    str += ".";
    }
    str += tmp[i];
    return str;
    }

    bool check(string s) {
    stringstream ss(s);
    int num;
    ss >> num;
    if (num > 255) {
    return false;
    }

    if (s[0] == '0' && s.size() != 1) {
    return false;
    }
    return true;
    }
    };