算法笔记（八）——字符串

最长公共前缀

题目：最长公共前缀

思路

• 两两比较，将每两个的子串和未比较的字符串相比较；
  

C++代码

class Solution 
{
public:string Common(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 = 1; i < strs.size(); i++)ret = Common(ret, strs[i]);return ret;}
};

最长回文子串

题目：最长回文子串

思路

• 中心扩散：计算以每一个字母为中心向左右两边扩散的奇数和偶数的回文串最大长度和该回文串的起始位置

C++代码

class Solution 
{
public:string longestPalindrome(string s) {int begin = 0, len = 0;int 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);}
};

二进制求和

题目：二进制求和

思路

• 从字符串右边开始累加进位拼接字符串，计算完之后记得翻转字符串

C++代码

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

字符串相乘

题目：字符串相乘

思路

• 计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后再去进位

C++代码

class Solution 
{
public:string multiply(string num1, string num2) {int n = num1.size(), m = num2.size();// 反转两个字符串reverse(num1.begin(), num1.end());   reverse(num2.begin(), num2.end());   // 存放每一位相乘的结果vector<int> tmp(n + m - 1);// 无进位相乘for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');}}// 处理进位int cur = 0, t = 0;string ret;while(cur < n + m - 1 || t != 0){if(cur < n + m + 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;}
};