【LeetCode热题100】字符串

本篇博客记录了关于字符串相关的几道题目，包括最长公共前缀、最长回文子串、二进制求和、字符串相乘。

//解法1
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {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 i = 0;while(i < min(s1.size(),s2.size()) && s1[i] == s2[i]) i++;return s1.substr(0, i);}
};
//解法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() || strs[j][i] != tmp) return strs[0].substr(0,i);}}return strs[0];}
};

题目分析：本道题有两种思路：

第一种方法是两个进行查找最长公共子串，最后返回这两个字符串的公共子串，再把这个公共子串和下一个字符串进行查找，返回这两个字符串的公共子串，依次查找下去。

第二种方法是同时比较所有子串，先比较第一个字符串的第一个字母和剩下字符串的第一个字母，然后再比较第一个字符串的剩下字符串的第二个字母，依次类推。

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);}
};

题目分析：这道题是要找回文子串，而回文子串是对称的，我们可以利用这样的特性来结题。把这个字符串的每个字母依次作为中心点i，如果回文子串是奇数个，那么先让right和left都指向i，判断s[left]和s[right]是否相等，如果相等，那么让left--，right++；如果回文子串是偶数个，让left指向i，right指向i+1（或者让left指向i-1，right指向i），判断s[left]和s[right]是否相等，如果相等，那么让left--，right++。

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

题目分析：这道题就是模拟相加过程，把两个字符串的最低位加到tmp变量上，然后%2得到最后结果的倒数第一位，然后tmp/2是进位，然后再去把倒数第二位都加到tmp，再%2最后结果的倒数第二位，然后tmp/2是进位，依次这样下去。

class Solution {
public:string multiply(string num1, string num2) {//1.处理为0的情况if(num1 == "0" || num2 == "0") return "0";string ret;int m = num1.size();int n = num2.size();vector<int> tmp(m + n - 1, 0);reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());//2.先无进位相乘后相加for(int i = 0; i < n ; i++){for(int j = 0 ; j < m ; j++){tmp[i + j] += (num2[i] - '0')*(num1[j] - '0');}}//3.处理进位int cur = 0 , t = 0;while(cur < m + n -1 || t){if(cur < m + n -1) t += tmp[cur++];ret += t % 10 + '0';t /= 10;}reverse(ret.begin(), ret.end());return ret;}
};

题目分析：有两种思路，无论哪种思路，都要将两个字符串先逆序，这样下标0、1、2代表的是真实列竖式运算从低位到高位的顺序：1）模拟列竖式计算，string ret = "0"，string tmp，tmp存的是每次相乘后的结果，然后把tmp累加到ret上，再计算下一位相乘的结果，再累加到ret上。要注意几个细节：高位相乘的时候要补上0，处理为0的情况。

2）无进位相乘，然后相加，最后处理进位。创建一个大小为m+n-1的数组tmp，tmp存放无进位累加的结果，然后处理tmp的进位问题。