本期内容我们来讲解C++算法中另一个重要的专题：字符串

        相关题解代码已经上传至作者的个人gitee：楼田莉子/C++算法学习喜欢请点个赞谢谢

前言

        字符串

        字符串是编程中最基本的数据类型之一，用于表示文本信息。它是由零个或多个字符组成的序列，通常用单引号(')或双引号(")括起来表示。

        基本特性

1. 不可变性：在大多数编程语言中，字符串是不可变的，意味着一旦创建就不能被修改。任何看似修改字符串的操作实际上都是创建了一个新的字符串。

2. 编码方式：现代编程语言通常使用Unicode编码来表示字符串，支持多语言字符集。常见的编码方式包括UTF-8、UTF-16等。

3. 索引访问：字符串中的字符可以通过索引位置访问，索引通常从0开始。例如"hello"[1]会返回'e'。

        实际应用场景

1. 用户输入处理：验证和转换用户输入的文本数据
2. 文件路径操作：拼接和处理文件路径
3. 数据清洗：处理和分析文本数据
4. 日志记录：生成格式化的日志信息
5. Web开发：处理URL、HTML内容等

1、最长公共前缀

        算法思想：

1、两两比较

class Solution {
public:
    //算法一：两两比较
    string findcommon(string s1,string s2)
    {
        int i=0;
        
        while(i<min(s1.size(),s2.size())&&s1[i]==s2[i]) i++;
        return s1.substr(0,i);
    }
    string longestCommonPrefix(vector<string>& strs) 
    {
        //算法一：两两比较
        string ret=strs[0];
        for(int i=0;i<strs.size();i++)
            ret=findcommon(ret,strs[i]);
        return ret;
    }
};

2、统一比较

class Solution {
public:
    //算法二：统一比较
    string longestCommonPrefix(vector<string>& strs) 
    {
        for(int i=0;i<strs[0].size();i++)
        {
            char tmp=strs[0][i];
            for(int j=1;j<strs.size();j++)
                if(i==strs[j].size()||tmp!=strs[j][i])
                    return strs[0].substr(0,i);
        }
        return strs[0];

    }
};

2、最长回文字串

        算法思想：中心扩展算法

        1、固定一个中心点

        2、从中心点向两侧扩展：奇数长度和偶数长度都要考虑

class Solution {
public:
    string longestPalindrome(string s)
    {
        //题解答案
        int begin = 0, len = 0, n = s.size();
        for (int i = 0; i < s.size(); i++)//依次枚举所有的中点
        {
            int left = i, right = i;
            //奇数次长度
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
            //偶数次长度
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }

        }
        return s.substr(begin, len);
    }
};

3、二进制求和

        算法思想：模拟竖式运算

class Solution {
public:
    string addBinary(string a, string b) 
    {
        string ret;
        int s1=a.size()-1,s2=b.size()-1,t=0;
        while(s1>=0||s2>=0||t)
        {
            if(s1>=0) t+=a[s1--]-'0'; 
            if(s2>=0) t+=b[s2--]-'0';
            ret+=t%2+'0';
            t/=2;
        }
        reverse(ret.begin(),ret.end());
        return ret;

    }
};

4、字符串相乘

        算法思想：

        1、模拟

        细节1、高位相乘要补“0”

        细节2、处理前导“0”

        细节3、注意计算结果的顺序

        优化：无进位相乘后相加，最后处理加法进位

        

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        //题解：无进位相乘后相加，最后处理加法进位
        //准备
        int m=num1.size(),n=num2.size();
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        vector<int>tmp(m+n-1);
        //无进位相乘后相加
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                tmp[i+j]+=(num1[i]-'0')*(num2[j]-'0');
        //处理加法进位
        int cur=0,t=0;//t标记进位
        string ret;
        while(cur<m+n-1||t!=0)
        {
            if(cur<m+n-1) t +=tmp[cur++];
            ret+=t%10+'0';
            t/=10;
        }
        //处理前导零
        while(ret.size()>1&&ret.back()=='0') ret.pop_back();
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

        本期内容就到这里了。字符串是竞赛和面试中的常客，后续我也会多加学习

        喜欢请点个赞支持一下谢谢