Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class IpAddresses
- {
- public:
- int dp[105][105];
- string n;
- int k;
- bool cmp(string A, string B) {
- if(A.size() > B.size()) {
- return false;
- }
- if(A.size() < B.size()) {
- return true;
- }
- if(A < B) {
- return true;
- }
- if(A == B) {
- return true;
- }
- return false;
- }
- int rec(int i, int br) {
- if(i == n.size() - 1 and k == br) {
- return 1;
- }
- if(i != -1 and dp[i][br] != -1) {
- return dp[i][br];
- }
- int result = 0;
- string tmp = "";
- for(int j = i + 1; j < n.size(); j++) {
- tmp += n[j];
- if(tmp.size() >= 2 and tmp[0] == '0') {
- continue;
- }
- if(cmp(tmp, "255")) {
- result += rec(j, br + 1);
- result %= 1000000007;
- }
- else {
- break;
- }
- }
- return dp[i][br] = result;
- }
- int count( string S, int K )
- {
- n = S;
- k = K;
- memset(dp, -1, sizeof dp);
- return rec(-1, 0);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement