C++优选算法十一 字符串

C++ 标准库中的 std::string 是一个用于表示和操作字符串的类。它提供了丰富的成员函数和运算符，使得字符串的处理变得既方便又高效。以下是一些关于 std::string 的关键特性和用法：

1. 引入头文件

要使用 std::string，你需要包含 <string> 头文件：

2. 声明和初始化

你可以通过多种方式声明和初始化 std::string 对象：

3. 字符串操作

std::string 提供了许多成员函数来操作字符串，例如：

• 长度：

  size_t len = str.length(); // 或 str.size()

• 访问字符：

  	char ch = str[0]; // 访问第一个字符，注意越界检查
  	char ch2 = str.at(0); // 访问第一个字符，越界时会抛出 std::out_of_range 异常

• 拼接字符串：

  	str += " "; // 追加空格
  	str += "World"; // 追加字符串
  	str.append("!!!"); // 追加字符串

• 子字符串：

  std::string substr = str.substr(1, 3); // 从索引1开始，长度为3的子字符串

• 查找：

  	size_t pos = str.find("World"); // 查找子字符串的位置
  	if (pos != std::string::npos) {
  	// 找到
  	}

• 替换：

  std::string newStr = str.replace(0, 5, "Hi"); // 替换前5个字符为 "Hi"

• 插入：

  str.insert(1, "abc"); // 在索引1处插入 "abc"

• 删除：

  	str.erase(1, 3); // 从索引1开始删除3个字符
  	str.pop_back(); // 删除最后一个字符

4. 字符串比较

std::string 支持多种比较运算符：

5. 字符串流

你可以使用 std::stringstream 将字符串与其他数据类型进行转换：

6. 非成员函数

C++ 标准库还提供了一些非成员函数来操作 std::string，例如 std::getline 用于从输入流中读取一行：

7. 性能注意事项

std::string 的实现通常基于动态数组（如 std::vector），因此它在大多数情况下性能很好，但在频繁进行拼接操作时，可能会因为内存重新分配而性能下降。在这种情况下，可以考虑使用 std::ostringstream 或预先分配足够的空间。

总结

std::string 是 C++ 标准库中非常强大且灵活的字符串处理类，它提供了丰富的成员函数和运算符，使得字符串的操作变得简单而高效。通过合理使用这些功能，你可以高效地处理各种字符串相关的任务。

8.示例题目

1.最长公共前缀. - 力扣（LeetCode）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

解法:
算法思路:
解法一(两两比较):
然后拿这个最长公共前缀依次与后面的字符串比较，这样就我们可以先找出前两个的最长公共前缀，可以找出所有字符串的最长公共前缀。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        //解法一 两两比较
        string ret=strs[0];
        for(int i=0;i<strs.size();i++)
        {
            ret=findCommon(ret,strs[i]);
        }
        return ret;        
    }

    string findCommon(string&s1,string& s2)
    {
        int i=0;
        while(i<min(s1.size(),s2.size())&&s1[i]==s2[i])
            i++;
        return substr(0,i);//截取子串
    }
};

解法二(统一比较)
题目要求多个字符串的公共前缀，我们可以逐位比较这些字符串，哪一位出现了不同，就在哪一位截止。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        if(strs.size()==1)
            return strs[0];
        string str;
        for(int i=0;i<strs[0].size();i++)
        {
            for(int j=0;j<strs.size()-1;j++)
            {
                if(strs[j][i]!=strs[j+1][i])
                {
                    return strs[0].substr(0,i);
                } 
            }
            str+=strs[0][i];
        }
        return str;
    }
};

2.最长回文子串. - 力扣（LeetCode）

给你一个字符串 s，找到 s 中最长的 回文子串 。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

解法(中心扩散)
算法思路:
枚举每一个可能的子串非常费时，有没有比较简单一点的方法呢?
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。如此这样去除，一直除到长度小于等于2时呢?长度为1的，自身与自身就构成回文;而长度为2的，就要判断这两个字符是否相等了。
从这个性质可以反推出来，从回文串的中心开始，往左读和往右读也是一样的。那么，是否可以枚举回文串的中心呢?
从中心向两边扩展，如果两边的字母相同，我们就可以继续扩展;如果不同，我们就停止扩展。这样只需要一层 for 循环，我们就可以完成先前两层 for 循环的工作量。

class Solution {
public:
    string longestPalindrome(string s)
    {
       int begin=0,len=0,n=s.size();
       for(int i=0;i<n;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.二进制求和. - 力扣（LeetCode）
 

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

解法(模拟十进制的大数相加的过程)
算法思路:
模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和，我们不是逢十进一，而是逢二进一。

class Solution {
public:
    string addBinary(string a, string b) 
    {
        string str;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int i=0;
        int tmp=0;
        int num=0;
        while(i<a.size()&&i<b.size())
        {
            num=(a[i]-'0')+(b[i]-'0')+tmp;
            tmp=num/2;
            str+=to_string(num%2);
            num=0;
            i++;
        }
        while(i<a.size())
        {
            num=(a[i]-'0')+tmp;
            tmp=num/2;
            str+=to_string(num%2);
            num=0;
            i++;
        }
        while(i<b.size())
        {
            num=(b[i]-'0')+tmp;
            tmp=num/2;
            str+=to_string(num%2);
            num=0;
            i++;
        }
        if(tmp!=0)
            str+=to_string(tmp);
        reverse(str.begin(),str.end());

        return str;
    }
};

4.字符串相乘. - 力扣（LeetCode）

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

解法(无进位相乘然后相加，最后处理进位)
算法思路:
整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性，我们选择一种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。如下图:​​​​​​​

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        //解法：无进位相乘后相加，然后处理进位
        int n=num1.size();
        int m=num2.size();
        if(num1=="0")
            return "0";
        if(num2=="0")
            return "0";
        vector<int> tmp(m+n-1);

        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        //1.无进位相乘后相加
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                tmp[i+j]+=(num1[i]-'0')*(num2[j]-'0');
            }
        }
        //2.处理进位
        string str;
        int t=0;
        for(int i=0;i<m+n-1;i++)
        {
            str += to_string((tmp[i]+t) % 10);
            t = (tmp[i] + t) / 10;
        }
        if(t!=0)
            str+=to_string(t);

        //处理前导零
        while(str.size()>1&&str.back()=='0')
            str.pop_back();
        reverse(str.begin(),str.end());

        return str;
    }
};