专题十一_字符串

目录

14. 最长公共前缀

解析

题解

5. 最长回文子串

解析

题解

67. 二进制求和

解析

题解

43. 字符串相乘

解析

题解

---

14. 最长公共前缀

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

 

 

解析

题解

解法一：两两比较，横向比较

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 65.专题十一_字符串_最长公共前缀_C++// 两两比较，横向比较if(strs.size() == 0) return "";if(strs.size() == 1) return strs[0];string ret = strs[0];for(int i = 1; i < strs.size(); ++i)ret = findCommon(ret, strs[i]);return ret;        }string findCommon(const string& s1, const string& s2){int index = 0;while(index < min(s1.size(), s2.size())){if(s1[index] == s2[index]) index++;else break;}return s1.substr(0, index);}
};

解法二：纵向对比

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 65.专题十一_字符串_最长公共前缀_C++// 解法二：纵向对比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];}
};

5. 最长回文子串

5. 最长回文子串

 

 

解析

题解

方法一：动态规划

class Solution {
public:string longestPalindrome(string s) {// 36.回文串问题_最长回文串_C++// 方法一：动态规划// 1.创建dp表// 2.初始化// 3.填表// 4.返回值int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));int len = 1, begin = 0;for(int i = n - 1; i >= 0; --i){for(int j = i; j < n; ++j){if(s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;if(dp[i][j] && j - i + 1 > len) begin = i, len = j - i + 1;}}return s.substr(begin, len);}
};

方法二：中心扩展算法

class Solution {
public:string longestPalindrome(string s) {// 66.专题十一_字符串_最长回文子串_C++// 方法二：中心扩展算法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]){right++;left--;}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]){right++;left--;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}}return s.substr(begin, len);}
};

67. 二进制求和

67. 二进制求和

解析

 

题解

class Solution {
public:string addBinary(string a, string b) {// 67.专题十一_字符串_二进制求和_C++string ret;int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0; // 进位while(cur1 >= 0 || cur2 >= 0 || t){if(cur1 >= 0) t += a[cur1--] - '0';if(cur2 >= 0) t += b[cur2--] - '0';ret.push_back(t % 2 + '0');t /= 2;}reverse(ret.begin(), ret.end());    // 插入的结果是倒着的return ret;}
};

43. 字符串相乘

43. 字符串相乘

 

 

解析

 

题解

class Solution {
public:string multiply(string num1, string num2) {// 68.专题十一_字符串_字符串相乘_C++// 解法二：先无进位相乘然后相加，最后处理进位// 1.准备工作int m = num1.size(), n = num2.size();reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());vector<int> tmp(m + n - 1);// 2.先无进位相乘然后相加for(int i = 0; i < m; ++i)for(int j = 0; j < n; ++j)tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');// 3.处理进位int cur = 0, t = 0;string ret;while(cur < m + n - 1 || t != 0){if(cur < m + n - 1) t += tmp[cur++];ret += t % 10 + '0';t /= 10;}// 4.处理前导0while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};