带加法序列的字符串-yiteyi-C++库

给定一个字符串，任务是找出它是否包含加法序列。一个字符串包含一个加法序列，如果它的数字可以组成一个数字序列，其中每个数字都是前两个数字的加法。一个有效字符串应至少包含三个数字，以构成一个加法序列。例如：

null

Input : s = “235813”Output : true2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13Input : s = “199100199”Output : true1 + 99 = 100, 99 + 100 = 199Input : s = “12345678”Output : false

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这个问题可以递归解决，请注意，增值中的位数不能小于其任何操作数中的位数，这就是为什么我们将循环到（字符串长度）/2（第一个数字）和（字符串长度–第一个数字的长度）/2（第二个数字）忽略无效结果。接下来要注意的是，第一个和第二个数字不能以0开头，这是isValid方法在下面的代码中签入的。当我们递归调用时，我们检查第一个和第二个数字的和是否完全等于字符串的其余部分。如果是，则直接返回结果，否则检查sum string是否为字符串其余部分的前缀；如果是，则在从字符串其余部分删除sum string后，使用第二个数字、sum string和字符串其余部分递归调用；如果sum string不是字符串其余部分的前缀，则没有可用的解决方案。下面是C++实现。

CPP

                         // C++ program to check whether a string                       
                         // makes an additive sequence or not                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Checks whether num is valid or not, by                       
                         // checking first character and size                       
                         bool                                     isValid(string num)                       
                         {                       
                                                 if                                     (num.size() > 1 && num[0] ==                                     '0'                                     )                       
                                                 return                                     false                                     ;                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // returns int value at pos string, if pos is                       
                         // out of bound then returns 0                       
                         int                                     val(string a,                                     int                                     pos)                       
                         {                       
                                                 if                                     (pos >= a.length())                       
                                                 return                                     0;                       
           
                                                 //  converting character to integer                       
                                                 return                                     (a[pos] -                                     '0'                                     );                       
                         }                       
           
                         // add two number in string form and return                       
                         // result as a string                       
                         string addString(string a, string b)                       
                         {                       
                                                 string sum =                                     ""                                     ;                       
                                                 int                                     i = a.length() - 1;                       
                                                 int                                     j = b.length() - 1;                       
                                                 int                                     carry = 0;                       
           
                                                 //  loop until both string get processed                       
                                                 while                                     (i >= 0 || j >= 0)                       
                                                 {                       
                                                 int                                     t = val(a, i) + val(b, j) + carry;                       
                                                 sum += (t % 10 +                                     '0'                                     );                       
                                                 carry = t / 10;                       
                                                 i--;    j--;                       
                                                 }                       
                                                 if                                     (carry)                       
                                                 sum += (carry +                                     '0'                                     );                       
                                                 reverse(sum.begin(), sum.end());                       
                                                 return                                     sum;                       
                         }                       
           
                         //  Recursive method to check c = a + b                       
                         bool                                     checkAddition(list<string>& res, string a,                       
                                                 string b, string c)                       
                         {                       
                                                 //  both first and second number should be valid                       
                                                 if                                     (!isValid(a) || !isValid(b))                       
                                                 return                                     false                                     ;                       
                                                 string sum = addString(a, b);                       
           
                                                 //  if sum is same as c then direct return                       
                                                 if                                     (sum == c)                       
                                                 {                       
                                                 res.push_back(sum);                       
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 /*  if sum size is greater than c, then no                       
                                                 possible sequence further OR if c is not                       
                                                 prefix of sum string, then no possible                       
                                                 sequence further  */                       
                                                 if                                     (c.size() <= sum.size() ||                       
                                                 sum != c.substr(0, sum.size()))                       
                                                 return                                     false                                     ;                       
                                                 else                       
                                                 {                       
                                                 res.push_back(sum);                       
                                   
                                                 //  next recursive call will have b as first                       
                                                 //  number, sum as second number and string                       
                                                 //  c as third number after removing prefix                       
                                                 //  sum string from c                       
                                                 return                                     checkAddition(res, b, sum,                       
                                                 c.substr(sum.size()));                       
                                                 }                       
                         }                       
           
                         //  Method returns additive sequence from string as                       
                         // a list                       
                         list<string> additiveSequence(string num)                       
                         {                       
                                                 list<string> res;                       
                                                 int                                     l = num.length();                       
           
                                                 // loop until l/2 only, because if first                       
                                                 // number is larger,then no possible sequence                       
                                                 // later                       
                                                 for                                     (                                     int                                     i = 1; i <= l/2; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 1; j <= (l - i)/2; j++)                       
                                                 {                       
                                                 if                                     (checkAddition(res, num.substr(0, i),                       
                                                 num.substr(i, j),                       
                                                 num.substr(i + j)))                       
                                                 {                       
                                                 // adding first and second number at                       
                                                 // front of result list                       
                                                 res.push_front(num.substr(i, j));                       
                                                 res.push_front(num.substr(0, i));                       
                                                 return                                     res;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // If code execution reaches here, then string                       
                                                 // doesn't have any additive sequence                       
                                                 res.clear();                       
                                                 return                                     res;                       
                         }                       
           
                         //  Method to print result list                       
                         void                                     printResult(list<string> res)                       
                         {                       
                                                 for                                     (                                     auto                                     it = res.begin(); it != res.end(); it++)                       
                                                 cout << *it <<                                     " "                                     ;                       
                                                 cout << endl;                       
                         }                       
           
                         //  Driver code to test above methods                       
                         int                                     main()                       
                         {                       
                                                 string num =                                     "235813"                                     ;                       
                                                 list<string> res = additiveSequence(num);                       
                                                 printResult(res);                       
           
                                                 num =                                     "199100199"                                     ;                       
                                                 res = additiveSequence(num);                       
                                                 printResult(res);                       
                                                 return                                     0;                       
                         }                       

输出：

2 3 5 8 13 1 99 100 199

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章