字符串问题(下)

一、验证IP地址

解法一:分割字符串比较法（推荐）

我们可以先对IP字符串进行分割，然后依次判断每个分割是否符合要求。

• 写一个split函数（或者内置函数）。
• 遍历IP字符串，遇到.或者:将其分开储存在一个数组中。
• 遍历数组，对于IPv4，需要依次验证分组为4，分割不能缺省，没有前缀0或者其他字符，数字在0-255范围内。
• 对于IPv6，需要依次验证分组为8，分割不能缺省，每组不能超过4位，不能出现除数字小大写a-f以外的字符。
• 

class Solution {
    
public:
    //将字符串从.或者:分割开
    vector<string> split(string s, string spliter) {
      
        vector<string> res;
        int i;
        //遍历字符串查找spliter
        while((i = s.find(spliter)) && i != s.npos){
      
            //将分割的部分加入vector中
            res.push_back(s.substr(0, i));  
            s = s.substr(i + 1);
        }
        res.push_back(s);
        return res;
    }
    bool isIPv4 (string IP) {
    
        vector<string> s = split(IP, ".");  
        //IPv4必定为4组
        if(s.size() != 4)  
            return false;
        for(int i = 0; i < s.size(); i++){
    
            //不可缺省，有一个分割为零，说明两个点相连
            if (s[i].size() == 0)  
                return false;
            //比较数字位数及不为零时不能有前缀零
            if (s[i].size() < 0 || s[i].size() > 3 || (s[i][0]=='0' && s[i].size() != 1))  
                return false;
            //遍历每个分割字符串，必须为数字
            for (int j = 0; j < s[i].size(); j++)  
                if (!isdigit(s[i][j])) 
                    return false;
            //转化为数字比较，0-255之间
            int num = stoi(s[i]);  
            if (num < 0 || num > 255) 
                return false;
        }    
        return true;
    }
    bool isIPv6 (string IP) {
    
        vector<string> s = split(IP, ":");
        //IPv6必定为8组
        if(s.size() != 8)  
            return false;
        for(int i = 0; i < s.size(); i++){
     
            //每个分割不能缺省，不能超过4位
            if(s[i].size() == 0 || s[i].size() > 4)  
                return false; 
            for(int j = 0; j < s[i].size(); j++){
    
                //不能出现a-fA-F以外的大小写字符
                if(!(isdigit(s[i][j]) || (s[i][j] >= 'a' && s[i][j] <= 'f') || (s[i][j] >= 'A' && s[i][j] <= 'F')))
                    return false;
            }
        }
        return true;
    }
    string solve(string IP) {
    
        if(IP.size() == 0)
            return "Neither";
        if(isIPv4(IP))
            return "IPv4";
        else if(isIPv6(IP))
            return "IPv6";
        return "Neither";
    }
};

时间复杂度：O(n)，n为字符串IP的长度，判断部分只遍历4组或者8组，但是分割字符串需要遍历全部
空间复杂度：O(1)，储存分割字符串的临时空间为常数4或者8

解法二:正则表达式

IP地址是有规律可言的：IPv4用了4个0-255的数字，用点隔开，IPv6用了4位十六进制的数字，用冒号隔开，共8组，这都可以直接用正则表达式来表示。

• IPv4的正则表达式限制数字在0-255，且没有前缀0，用3个点隔开共4组。
• IPv6的正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个，用冒号隔开。
• 调用函数依次比较给定字符串与模板串之间是否匹配，匹配哪一个就属于哪一种IP地址，否则都不是。

//必须加正则表达式的库
#include <regex> 
class Solution {
    
public:
    string solve(string IP) {
    
        //正则表达式限制0-255 且没有前缀0 四组齐全
        regex ipv4("(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])");
        //正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个
        regex ipv6("([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}");
        //调用正则匹配函数
        if (regex_match(IP, ipv4)) 
            return "IPv4";
        else if (regex_match(IP, ipv6)) 
            return "IPv6";
        else return "Neither";
    }
};

时间复杂度：O(n)，regex_match函数默认O(n)
空间复杂度：O(1)，没有使用额外空间

二、大数加法

解法一:模拟(推荐)

大整数相加，就可以按照整数相加的方式，从个位开始，逐渐往上累加，换到字符串中就是从两个字符串的末尾开始相加。

• 若是其中一个字符串为空，直接返回另一个，不用加了。
• 交换两个字符串的位置，我们是s为较长的字符串，t为较短的字符串，结果也记录在较长的字符串中。
• 从后往前遍历字符串s，每次取出字符转数字，加上进位制，将下标转换为字符串t中从后往前相应的下标，如果下标为非负数则还需要加上字符串t中相应字符转化的数字。
• 整型除法取进位，取模算法去掉十位，将计算后的结果放入较长数组对应位置。
• 如果遍历结束，进位值还有，则需要直接在字符串s前增加一个字符‘1’。

class Solution {
    
public:
    string solve(string s, string t) {
    
        //若是其中一个为空，返回另一个
        if(s.empty())
            return t;
        if(t.empty())
            return s;
        //让s为较长的，t为较短的
        if(s.length() < t.length()) 
            swap(s, t);
        //进位标志
        int carry = 0; 
        //从后往前遍历较长的字符串
        for(int i = s.length() - 1; i >= 0; i--){
     
            //转数字加上进位
            int temp = s[i] - '0' + carry; 
            //转较短的字符串相应的从后往前的下标
            int j = i - s.length() + t.length(); 
            //如果较短字符串还有
            if(j >= 0) 
                //转数组相加
                temp += t[j] - '0'; 
            //取进位
            carry = temp / 10; 
            //去十位
            temp = temp % 10; 
            //修改结果
            s[i] = temp + '0'; 
        }
        //最后的进位
        if(carry == 1) 
            s = '1' + s;
        return s;
    }
};

时间复杂度：O(n)，其中n为较长字符的长度，遍历字符串
空间复杂度：O(1)，常数级空间，没有使用额外辅助空间

解法二:逆序相加

我们可以模拟竖式加法进行运算，一开始先将两个字符串翻转，即从低位向高位计算；然后我们模拟竖式加法的原则，将对应数位的值相加，再加上上一步的进位值，假设和为d，则结果的当前位为d % 10，进位值为d / 10，以此类推
我们可以发现，两个数相加的结果最多为最高数位+1，例如一个2位数和4位数相加，结果最多为5位数，以此当运算到最高数位后，进位值d可能不为0，则需要添加一位d

class Solution {
    
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */
    string solve(string s, string t) {
    
        if(s.size() < t.size()) return solve(t, s);    // 若s的长度小于t, 交换一下两者的位置
        reverse(s.begin(), s.end());    // 翻转s
        reverse(t.begin(), t.end());    // 翻转t
        string ans;    
        int d = 0;    // 进位值
        for(int i = 0; i < s.size(); i++){
        // 以最大的数位基准
            d += s[i] - '0';
            if(i < t.size()) d += t[i] - '0';    // 若t当前位不为0
            ans += d % 10 + '0';    // 当前位的结果
            d /= 10;    // 下一步的进位值
        }
        if(d) ans += d % 10 + '0';    // 若d不为0，增加一位
        reverse(ans.begin(), ans.end());    // 将答案翻转
        return ans;
    }
};

时间复杂度：O(max(n, m))，n为s的长度，m为t的长度
空间复杂度：O(1)

解法三:C语言简洁版

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 * * C语言声明定义全局变量请加上static，防止重复定义 */
char* solve(char* s, char* t ) {
    
    // write code here
    int lens=strlen(s);
    int lent=strlen(t);
    int lenmax=(lens>lent?lens:lent)+2;
    int curindex=lenmax-1;
    int temp=0,ret=0;
    char*p=(char*)calloc(lenmax, sizeof(char));
    while(lens||lent)
    {
    
        temp=ret;
        if(lent)
            temp+=t[--lent]-'0';
        if(lens)
            temp+=s[--lens]-'0';
        ret=temp/10;
        temp%=10;
        p[--curindex]=temp+'0';
    }
    p[0]=ret+'0';
    return ret?p:(p+1);
}

时间复杂度：O(max(n, m))，n为s的长度，m为t的长度
空间复杂度：O(1)