A Dynamic programming approach


  • 0
    Y

    So you start with three vectors of vector representing the solutions up to the last 3 digits.
    Iterate through each character, and assemble the solution up to i-th char, swap each of first 3 vectors with the one most recently assembled.
    Code is kind of self-explanatory.

    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> res;
            int size = s.size();
            if(size<4 || size >12)
                return res;
            vector<int> temp;
            vector< vector<int> > dp0( 1, temp);
            vector< vector<int> > dp1=dp0;
            vector< vector<int> > dp2=dp0;
            for( int i = 1 ; i <=size; i++){
                char cur = s[i-1];
                vector< vector<int> > cur_dp;
                for( vector<int> x : dp2){
                    x.push_back( std::stoi( s.substr(i-1 , 1)) );
                    cur_dp.push_back(x);
                }
                
                if( i > 1 && s[i-1-1]!='0' ){
                    for( vector<int> x : dp1){
                        x.push_back( std::stoi( s.substr(i-2, 2)) );
                        cur_dp.push_back(x);    
                        
                    }
                }
                
                if( i > 2 && s[i-3]!='0' && std::stoi( s.substr(i-3  , 3 )) <=255 ){
                    for( vector<int> x : dp0){
                        x.push_back( std::stoi( s.substr(i-3,3) ));
                        cur_dp.push_back(x);
                    }
                }
                dp0=dp1;
                dp1=dp2;
                dp2=cur_dp;
            }
            for( vector<int> x : dp2){
                if( x.size()==4){
                    res.push_back( join(x) );
                }
            }
            return res;
        }
        string join(vector<int>& r){
            string res;
            for( int i=0;  i< r.size(); i++){
                res+=std::to_string(r[i]);
                if(i != r.size() -1)
                    res+='.';
            }
            return res;
        }
    };
    

Log in to reply
 

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