# A Dynamic programming approach

• 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> 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;
}
};
``````

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