常见字符串相关题目
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏： 优选算法专题
目录
14.最长公共前缀
5.最长回文子串
67.二进制求和
43.字符串相乘
14.最长公共前缀
题目：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]如果非空，则仅由小写英文字母组成
思路：我们有两种方式来查找字符串的最长公共长缀。一种方式是：两两比较，先查找两个字符串的最长公共前缀，得到的结果再去比较后面的字符串，一直比较直至最终遍历完数组即可。另外一种方式是：统一比较，以第一个字符串为基准字符串，从第一个字符字母开始与后续数组元素进行比较，如果遇到了字符串的末尾或者字符串的字母不相等，就可以直接返回最终的结果了。
代码实现：
两两比较的方式：
class Solution {
public String longestCommonPrefix(String[] strs) {
// 两两比较：比较两个字符串，得到最长公共前缀
String ret = strs[0];
for (int i = 1; i < strs.length; i++) {
String s = strs[i];
int j = 0;
// 满足两者都不越界的情况
while (j < ret.length() && j < s.length()) {
if (ret.charAt(j) != s.charAt(j)) { // 不相等直接返回即可
break;
}
j++;
}
// 更新最长公共前缀
ret = ret.substring(0, j);
}
return ret;
}
}统一比较的方式：
class Solution {
public String longestCommonPrefix(String[] strs) {
// 统一比较：比较全部字符串的每个字符
String ret = strs[0];
for (int i = 0; i < ret.length(); i++) {
char ch = ret.charAt(i);
// 依次比较后面的元素相同位置是否是相同的字符
for (int j = 1; j < strs.length; j++) {
// 如果到达字符串的末尾了 或者 字符串的字符不相等了，直接返回即可
if (i == strs[j].length() || ch != strs[j].charAt(i)) {
return ret.substring(0, i);
}
}
}
return strs[0]; // 说明所有的元素都是相同的
}
}5.最长回文子串
题目：
给你一个字符串
s，找到s中最长的 回文 子串。示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd" 输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
思路：有一个专门寻找回文子串相关的算法：中心扩展算法。因为回文子串的特点是从左到右遍历得到的序列与从右到左得到的序列是一样的，那么从回文子串的中间位置往两边扩展的结果也是一致的。利用这个性质，我们就可以来做题了：遍历字符串，在每一个位置进行中心扩展算法，得到回文子串的序列，最后返回最长的回文子串序列即可。
代码实现：
class Solution {
public String longestPalindrome(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
int begin = 0, end = 0;
// 固定一个中心点
for (int i = 0; i < n; i++) {
// 从中心点开始往两侧扩展
// 先扩展奇数个
int left = i, right = i;
while (left >= 0 && right <= n-1 && s[left] == s[right]) {
left--;
right++;
}
// 更新begin 与 end
if (right-left-1 > end-begin+1) {
begin = left+1;
end = right-1;
}
// 再扩展偶数个
left = i;
right = i+1;
while (left >= 0 && right <= n-1 && s[left] == s[right]) {
left--;
right++;
}
//更新begin 与 end
if (right-left-1 > end-begin+1) {
begin = left+1;
end = right-1;
}
}
return ss.substring(begin, end+1);
}
}要注意的是在扩展的过程中，字符个数可能是奇数个，也可能是偶数个，因此我们扩展时也得分情况讨论。
67.二进制求和
题目：
给你两个二进制字符串
a和b，以二进制字符串的形式返回它们的和。示例 1：
输入:a = "11", b = "1" 输出："100"示例 2：
输入：a = "1010", b = "1011" 输出："10101"提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
思路：遍历字符串，拿到两者相加的和，模上进位数作为当前位的结果，当两个字符串遍历完成且进位为0时，就可以返回最终结果了。
代码实现：
class Solution {
public String addBinary(String a, String b) {
// 遍历字符串模拟列竖式运算
int ai = a.length()-1, bi = b.length()-1, t = 0;
StringBuilder sb = new StringBuilder();
// 注意：题目给的是正序序列，但是计算时需要从后面(低位)开始计算
while (ai >= 0 || bi >= 0) {
// 先计算两者相同位相加的结果
if (ai >= 0) {
// t += a.charAt(ai); // 这里拿到的是字符1，而不是数字1
t += a.charAt(ai) - '0';
}
if (bi >= 0) {
// t += b.charAt(bi); // 这里拿到的是字符1，而不是数字1
t += b.charAt(bi) - '0';
}
sb.append(t % 2);
t /= 2;
ai--;
bi--;
}
// 可能最终的进位并不为0
if (t != 0) {
sb.append(t % 2);
}
// 注意：最终的结果要逆序
return sb.reverse().toString();
}
}43.字符串相乘
题目：
给定两个以字符串形式表示的非负整数
num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
思路：与上一题的二进制求和类似。也是采用模拟计算的方式来写，这里是模拟乘法的方式，即列竖式运算。如下所示：
遍历其中一个字符串，使其的每一个字符去乘以另外一个字符串，得到的结果进行相加求和，就是最终的结果。这里的求和就是上面二进制求和的写法。
上面这种暴力模拟是非常麻烦的，代码也是非常多的。还有一种是对乘法的简化：先是无进位相乘，再对结果进行相加，最后转换为正常位数的表示即可。
代码实现：
模拟列竖式运算：
class Solution {
// 对两个字符串数字进行相乘，返回字符串形式的积
public String multiply(String num1, String num2) {
// 判断字符串是否存在0
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
String ret = "";
// 模拟列竖式计算
int count = 0; // 统计先导0
for (int i = num2.length()-1; i >= 0; i--) {
StringBuilder temp = new StringBuilder();
// 计算先导0
for (int j = 0; j < count; j++) {
temp.append(0);
}
count++;
// 计算 num2的每一个位 与 num1 的乘积
int product = 0; // 存储乘积
int a = num2.charAt(i) - '0';
for (int j = num1.length()-1; j >= 0; j--) {
int b = num1.charAt(j) - '0';
product = a * b + product; // 原始乘积+进位
temp.append(product % 10);
product /= 10;
}
// 进位可能不为0
if (product != 0) {
temp.append(product % 10);
}
// 将乘积进行相加（"两数"之和）
ret = twoNumSum(ret, temp.reverse().toString());
}
return ret;
}
// 对两个字符串数字进行相加，返回字符串形式的和
public String twoNumSum(String s1, String s2) {
int i = s1.length()-1, j = s2.length()-1;
int sum = 0;
StringBuilder builder = new StringBuilder();
while (i >= 0 || j >= 0) {
if (i >= 0) {
sum += s1.charAt(i) - '0';
}
if (j >= 0) {
sum += s2.charAt(j) - '0';
}
builder.append(sum % 10);
sum /= 10;
i--;
j--;
}
// 可能存在进位
if (sum != 0) {
builder.append(sum % 10);
}
// 需要逆置
return builder.reverse().toString();
}
}模拟列竖式优化版：
class Solution {
// 对两个字符串数字进行相乘，返回字符串形式的积
public String multiply(String num1, String num2) {
// 判断字符串是否存在0
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
// 先逆序字符串
String s1 = new StringBuilder(num1).reverse().toString();
String s2 = new StringBuilder(num2).reverse().toString();
int n1 = s1.length(), n2 = s2.length();
// 申请一个数组存放乘积
int[] temp = new int[n1+n2-1];
// 计算 num2的每一个位 与 num1 的乘积
for (int i = 0; i < n2; i++) {
int a = s2.charAt(i) - '0';
for (int j = 0; j < n1; j++) {
int b = s1.charAt(j) - '0';
temp[i+j] += a*b; // 一定要加上原来的值
}
}
// 将数组的每一位转换成标准表示形式（"两数"相加的思路）
int i = 0;
StringBuilder builder = new StringBuilder();
int sum = 0;
while (i < n1+n2-1) {
sum += temp[i];
builder.append(sum % 10);
sum /= 10;
i++;
}
// 可能存在进位不为0的情况
if (sum != 0) {
builder.append(sum % 10);
}
// 注意要逆置
return builder.reverse().toString();
}
}好啦！本期 常见字符串相关题目 的刷题之旅 就到此结束啦！我们下一期再一起学习吧！