【Warrior刷题笔记】力扣306.累加数

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int m = num.size();//串长
        if(m<3) return false;//串长低于3则返回假
        for(int i = 1; i <= m/2; ++i){//枚举不同的加数1长度
            for(int j = 1; j+i+(i<j?j:i) <= m; ++j){//枚举不同的加数2长度
                string s1 = num.substr(0,i);//截取加数一
                string s2 = num.substr(i,j);//截取加数二
                if(s2.size()>1 && s2[0]=='0') continue;//若加数二含有前导零，跳出本次循环
                string s3 = add(s1, s2);//计算累加和
                int len = s3.size();//计算累加和长度
                int startS4 = i + j;//计算备选累加和截取开始位置
                string s4 = num.substr(startS4, len);//截取备选累加和
                if(s4.size()>1 && s4[0]=='0') continue;//若备选累加和含有前导零，跳出本次循环
                bool canReturn = true;//标记是否为累加序列，初始化为真
                while(startS4+len<=m){//依次遍历
                    if(s3==s4){//若备选累加和与实际计算值相等
                        s1 = s2;//更新s1
                        s2 = s3;//更新s2
                        s3 = add(s1, s2);//计算s3
                        startS4 += len;//计算s4开始位置
                        len = s3.size();//计算s4长度
                        s4 = num.substr(startS4,len);//截取s4
                        if(s2.size()>1 && s2[0]=='0'){//若s4含有前导零，则标记本次枚举不是累加序列，跳出本次循环
                            canReturn = false;
                            break; 
                        }
                    }
                    else{//若一直相等，标记为累加序列
                        canReturn = false;
                        break;
                    }
                }
                if(canReturn) return true;//返回真
            }
        }//遍历完都不满足累加序列条件，返回假
        return false;
    }

    inline string add(string& s1, string& s2){//辅助字符串加法
        int m = s1.size();//串1长
        int n = s2.size();//串2长
        int len = m<n ? n : m;//两串长度最大值
        string head;//补零字符串
        for(int i = 0; i < ((n-m>=0) ? n-m : m-n); ++i) head += '0';//填充补零字符串
        if(m<n) s1 = head + s1;//填充零
        else s2 = head + s2;
        int carry = 0;//进位初始化为0
        for(int i = len - 1; i >= 0; --i){//按位加
            int sum = (s1[i]-'0') + (s2[i]-'0') + carry;//求和
            if(sum>9){ //如果和大于9
                s1[i] = to_string(sum-10)[0];//当前位修改为to_string(sum-10)[0]
                carry = 1;//进位置为1
            }
            else{
                s1[i] = to_string(sum)[0];//否则当前位修改为to_string(sum)[0]
                carry = 0;//进位置于0
            }
        }
        if(carry==0) return s1;//若进位为零返回s1
        else return "1" + s1;//否则返回"1"+s1;
    }
};