Restore IP Addresses

Description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example

Given"25525511135", return

[
  "255.255.11.135",
  "255.255.111.35"
]

Related problems

Subsets

Implementation

Link: http://lintcode.com/en/problem/restore-ip-addresses/

class Solution {
public:
    /**
     * @param s the IP string
     * @return All possible valid IP addresses
     */
    vector<string> restoreIpAddresses(string& s) {
        // Write your code here
        vector<string> ret;
        string ans;
        int step = 0;
        int idx = 0;

        if(s.size() == 0) {
            return ret;
        }

        helper(ret, ans, s, step, idx);
        return ret;
    }

    void helper(vector<string> & ret,
                string& ans,
                string& s,
                int step,
                int idx)
    {
        // reach the end x.x.x.x
        if(step == 4) {
            // completely consume the string
            if(idx == s.size()) {
                ret.push_back(ans);
            }
            return;
        }

        for(int i = 0; i < 3; i++){
            // within the range
            if(idx + i > s.size() - 1) break;

            string str = s.substr(idx, i + 1);
            string keep = ans;

            // valid value
            if(stoi(str) > 255) break;
            // no 0# or 00#
            if(i > 0 && str[0] == '0') break;
            // not the first one
            if(idx != 0) ans += ".";

            ans += str;
            helper(ret, ans, s, step + 1, idx + i + 1);
            ans = keep;
        }
    }
};