10-字符串

字符串是通常是配合其他的算法/数据结构来出题的，因此它的题目的很多的。

题目

LC14. 最长公共前缀

这题目有两个思路：

• 第一个是两两字符串依次比较。
• 第二个是先比较所有字符串的第一个，然后再比较第二个，依次类推

两两比较

这个是可以使用分治的思想，采用递归的思路来写

public String longestCommonPrefix(String[] strs) {
	// 方法1 两两比较，可以通过分治的思想，递归比较
	return merge(0, strs.length - 1, strs);
}

private String merge(int left, int right, String[] strs) {
	if (left > right) return null;
	if (left == right) return strs[left];

	int mid = (right - left) / 2 + left;
	String leftStr = merge(left, mid, strs);
	String rightStr = merge(mid + 1, right, strs);

	// 考虑健壮性，如果是 null，那说明一方是无效的
	if (leftStr == null) return rightStr;
	if (rightStr == null) return leftStr;
	
	// 比较
	int len = Math.min(rightStr.length(), leftStr.length());
	int i = 0;
	for (; i < len && rightStr.charAt(i) == leftStr.charAt(i); i++);

	// 有效范围 [0, i)
	return leftStr.substring(0, i);
}

统一比较

所有字符串从第一个字符开始比较

public String longestCommonPrefix(String[] strs) {
	int n = strs.length;

	// 先求出它们最短的字符串长度
	int minLen = strs[0].length();
	for (int i = 1; i < n; i++) {
		minLen = Math.min(minLen, strs[i].length());
	}

	// 比较 要比较 minLen 轮
	boolean flag = true;
	int i = 0;
	for (; i < minLen; i++) {
		// 每一个字符都要比较一轮
		for (int j = 0; j < n - 1 && flag; j++) {
			if (strs[j].charAt(i) != strs[j + 1].charAt(i)) flag = false;
		}
		// 出来的时候判断一下，如果不满足那么就需要停止循环
		if (!flag) break;
	}

	return strs[0].substring(0, i);
}

LC5. 最长回文子串

采用中心扩展法：

1. 先固定一个位置 i，利用回文串的特性依次向两边遍历
2. 当然也要考虑到偶数的情况，那么就把右边的位置固定到 i + 1 上，然后依次向两边遍历

在偶数个的情况下，右边的位置是固定在 i + 1 的位置，那能不能变为左边的位置固定在 i - 1 上呢?

其实也是可以的，不过需要考虑边界的情况

int retLeft = 0;
int retRight = 0;
public String longestPalindrome(String s) {
	int n = s.length();
	for (int i = 0; i < n; i++) {
		// 先计算奇数长度的
		computeLongestLength(i - 1, i + 1, s);

		// 算偶数长度的
		// computeLongestLength(i - 1, i, s); // 这个其实也可以的，两个选一个就行
		computeLongestLength(i, i + 1, s);
	}
	return s.substring(retLeft, retRight + 1);
}

private void computeLongestLength(int tmpLeft, int tmpRight, String s) {
	int n = s.length();
	while (tmpLeft >= 0 && tmpRight < n && s.charAt(tmpLeft) == s.charAt(tmpRight)) {
		tmpLeft--;
		tmpRight++;
	}
	// tmpRight 和 tmpLeft 不是对应的下标，它们要向 i 方向靠拢一个单位
	tmpRight--;
	tmpLeft++;
	if (tmpRight - tmpLeft > retRight - retLeft) { 
		retRight = tmpRight;
		retLeft = tmpLeft;
	}
}

LC67. 二进制求和

这个和之前 链表的两数相加 一样，不过这里是正序的，因此需要考虑翻转的情况，或者使用一个指针指向最后的索引，

public String addBinary(String a, String b) {
	// 先翻转一下
	a = new StringBuilder(a).reverse().toString();
	b = new StringBuilder(b).reverse().toString();

	int tmpResult = 0;
	int aN = a.length(), bN = b.length();
	StringBuilder result = new StringBuilder();

	// 相加
	for (int i = 0; i < aN || i < bN || tmpResult != 0; i++) {
		if (i < aN) {
			tmpResult += a.charAt(i) - '0';
		}
		if (i < bN) {
			tmpResult += b.charAt(i) - '0';
		}
		result.append(tmpResult % 2);
		tmpResult /= 2;
	}

	// 最终的结果需要翻转一下
	return result.reverse().toString();
}

LC43. 字符串相乘

这个题目有两个解法：

1. 利用小学学过的列竖式运算，计算出所有的相乘的和，然后把这些和求出来就可以。（比较复杂）
2. 通过无进位相乘，算出没有进位的结果，最后把计算它们的进位就可以了（写法比较简单）

列竖式运算

public String multiply(String num1, String num2) {
	// 使用解法1 传统的相乘累加（有进位的）
	num1 = new StringBuilder(num1).reverse().toString();
	num2 = new StringBuilder(num2).reverse().toString();

	// 1. 先算出累加后的数组
	List<StringBuilder> addResultList = getAddResultList(num1, num2);

	for (StringBuilder x : addResultList) {
		System.out.println(x);
	}

	// 2. 把结果进行累加
	int maxLen = num1.length() + num2.length();
	return addResult(addResultList, maxLen);
}

private List<StringBuilder> getAddResultList(String num1, String num2) {
	List<StringBuilder> result = new ArrayList<>();

	// 如果原来的是 123, 43 那么现在就是 321, 34
	for (int i = 0; i < num1.length(); i++) {
		StringBuilder addResult = new StringBuilder();
		for (int j = 0; j < i; j++) {
			addResult.append(0); // 需要考虑 i 为非零的情况下，末尾为 0 的情况
		}
		// 开始计算
		int tmp = 0;
		for (int j = 0; j < num2.length(); j++) {
			tmp += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
			addResult.append(tmp % 10);
			tmp /= 10;
		}
		while (tmp != 0) {
			addResult.append(tmp % 10);
			tmp /= 10;
		}

		// 计算完毕，添加到列表上
		result.add(addResult);
	}
	return result;
}

private String addResult(List<StringBuilder> addResultList, int maxLen) {
	int tmp = 0;
	StringBuilder result = new StringBuilder();
	for (int i = 0; i < maxLen; i++) {
		// 在第 i 位累加
		for (StringBuilder addResult : addResultList) {
			if (i >= addResult.length()) continue;
			tmp += addResult.charAt(i) - '0';
		}
		// 只执行一次，因为目前是计算第 i 位
		result.append(tmp % 10);
		tmp /= 10;
	}
	// 处理残留的内容
	while (tmp != 0) {
		result.append(tmp % 10);
		tmp /= 10;
	}
	// 除去末尾的 0, 但是不能全部都去除，如果最后的结果为 0, 需要保留
	while (result.length() > 1 && result.charAt(result.length() - 1) == '0') {
		result.deleteCharAt(result.length() - 1);
	}
	return result.reverse().toString();
}

无进位相乘

public String multiply(String num1, String num2) {
	if ("0".equals(num1) || "0".equals(num2)) return "0";
	num1 = new StringBuilder(num1).reverse().toString();
	num2 = new StringBuilder(num2).reverse().toString();
	int n1 = num1.length(), n2 = num2.length();

	// 无进位求和
	int[] addResultList = new int[n1 + n2 - 1];
	for (int i = 0; i < n1; i++) {
		for (int j = 0; j < n2; j++) {
			addResultList[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
		}
	}

	// 计算有进位的
	StringBuilder result = new StringBuilder();
	int tmp = 0;
	for (int i = 0; i < addResultList.length; i++) {
		tmp += addResultList[i];
		result.append(tmp % 10);
		tmp /= 10;
	}
	while (tmp != 0) {
		result.append(tmp % 10);
		tmp /= 10;
	}

	return result.reverse().toString();
}