字符串问题

1,判断两个字符串是否互为变形词
题目：给定两个字符串str1和str2，如果str1和str2中出现的字符种类一样且每种字符出现的次数也一样，那么str1和str2互为变形词。请实现判断两个字符串是否为变形词的函数。
举例：str1=”123”，str2=”231”，返回true；str1=”123”，str2=”2331”，返回false。
思路：如果str1和str2长度不同，那么直接返回false。如果长度相同，假设出现字符的编码值在0-255之间，那么申请一个长度为255的整型数组map，map[a]=b代表字符编码为a的字符出现了b次，初始时map[0…255]的值都是0。然后遍历字符串str1，统计每种字符出现的数量，比如遍历到字符’a’，其编码为97，则令map[97]++。这样map就成了str1中每种字符的词频统计表。然后遍历字符串str2，每遍历到一个字符都在map中把词频减下来，比如遍历到字符’a’，其编码值为97，则令map[97]–，如果减少之后的值小于0，直接返回false，如果遍历完str2，map中的值也没出现负值，则返回true。
具体参看如下代码中的isDeformation方法

public static boolean isDeformation(String str1, String str2) {
		if (str1 == null || str2 == null || str1.length() != str2.length()) {
			return false;
		}
		char[] chas1 = str1.toCharArray();
		char[] chas2 = str2.toCharArray();
		int[] map = new int[256];
		for (int i = 0; i < chas1.length; i++) {
			map[chas1[i]]++;
		}
		for (int i = 0; i < chas2.length; i++) {
			if (map[chas2[i]]-- == 0) {
				return false;
			}
		}
		return true;
}

如果字符的类型很多，可以用哈希表代替长度为255的整型数组，但整体过程不变。如果字符的种类为M，str1和str2的长度为N，那么该方法的时间复杂度为O(N)，额外空间复杂度为O(M)。
2,字符串中数字字串的求和
题目：给定一个字符串str，求其中的全部数字串所代表的数字之和。
要求：
1，忽略小数点字符，例如”A1.3”，其中包含两个数字1和3。
2，如果紧贴数字字串的左侧出现字符”-“，当连续出现的数量为奇数时，则数字为负，连续出现的数量为偶数时，则数字为正。例如，”A-1BC–12”，其中包含数字为-1和12。
举例：str=”A1CD2E33”，返回36。str=”A-1B–2C–D6E”，返回7。
思路：本题能做到O(n)的时间复杂度，额外空间复杂度为O(1)，且有多种方法，本书提供一种供参考。解法的关键是如何在从左到右遍历str时，准确收集每个数字并累加起来。具体过程如下：
1),生成三个变量。整型变量res，表示目前的累加和；整型变量num，表示当前收集到的数字；布尔型变量posi，表示如果把num累加到res里，num是正还是负。初始时，res=0，num=0，posi=true。
2),从左到右遍历str，假设遍历到字符cha，根据具体的cha有不同的处理。
3),
请参看下面的numSum方法。

public static int numSum(String str) {
		if (str == null) {
			return 0;
		}
		char[] charArr = str.toCharArray();
		int res = 0;
		int num = 0;
		boolean posi = true;
		int cur = 0;
		for (int i = 0; i < charArr.length; i++) {
			cur = charArr[i] - '0';
			if (cur < 0 || cur > 9) {
				res += num;
				num = 0;
				if (charArr[i] == '-') {
					if (i - 1 > -1 && charArr[i - 1] == '-') {
						posi = !posi;
					} else {
						posi = false;
					}
				} else {
					posi = true;
				}
			} else {
				num = num * 10 + (posi ? cur : -cur);
			}
		}
		res += num;
		return res;
}

3，去掉字符串中连续出现k个0的字串
题目：给定一个字符串和一个整数k，如果str中正好有连续的k个’0’出现时，把k个连续的’0’字符去除，返回处理后的字符串。
举例，str=”A00B”,K=2,返回”A00B”。str=”A0000B000”,K=3,返回”A0000B”。
思路：
方法如下：

public static String removeKZeros(String str, int k) {
		if (str == null || k < 1) {
			return str;
		}
		char[] chas = str.toCharArray();
		int count = 0, start = -1;
		for (int i = 0; i != chas.length; i++) {
			if (chas[i] == '0') {
				count++;
				start = start == -1 ? i : start;
			} else {
				if (count == k) {
					while (count-- != 0)
						chas[start++] = 0;
				}
				count = 0;
				start = -1;
			}
		}
		if (count == k) {
			while (count-- != 0)
				chas[start++] = 0;
		}
		return String.valueOf(chas);
}

4，判断两个字符串是否互为旋转词
题目：一个字符串str，把字符串str前面任意的部分挪到后面形成的字符串叫作str的旋转词。比如str=”12345”，str的旋转词有”12345”、”23451”、”34512”、”45123”、”51234”。给定两个字符串a和b，请判断a和b是否互为旋转词。
举例：a=”cdab”,b=”abcd”,返回true；a=”1ab2”，b=”ab12”,返回false；
a=”2ab1”，b=”ab12”,返回true。
要求：如果a和b长度不一样，那么a和b必然不互为旋转词，可以直接返回false。当a和b长度一样，都为n时，要求的解法时间复杂度为O(n)。
思路：a和吧长度不一样，不可能互为旋转词。如果长度一样，先生成一个大字符串b2，b2是两个字符串b拼在一起的结果，即String b2 = b + b。然后看b2中是否包含字符串a，如果包含，说明字符串a和b互为旋转词，否则说明两个字符串不互为旋转词。这是为什么呢？举例说明，这对于所有的情况都是对的，所以这种方法是有效的。请参看下面的isRotation方法。

public static boolean isRotation(String a, String b) {
		if (a == null || b == null || a.length() != b.length()) {
			return false;
		}
		String b2 = b + b;
		return getIndexOf(b2, a) != -1;
}

KMP算法

// KMP Algorithm
	public static int getIndexOf(String s, String m) {
		if (s.length() < m.length()) {
			return -1;
		}
		char[] ss = s.toCharArray();
		char[] ms = m.toCharArray();
		int si = 0;
		int mi = 0;
		int[] next = getNextArray(ms);
		while (si < ss.length && mi < ms.length) {
			if (ss[si] == ms[mi]) {
				si++;
				mi++;
			} else if (next[mi] == -1) {
				si++;
			} else {
				mi = next[mi];
			}
		}
		return mi == ms.length ? si - mi : -1;
	}

以上是主方法，isRotation方法中getIndexOf方法的功能是如果b2中包含a，则返回a在b2中的开始位置，如果不包含a，则返回-1，即getIndexOf是解决匹配的问题的函数，如果想让整个过程在O(n)时间复杂度内完成，那么字符串匹配问题也需要在O(n)时间复杂度内完成。这正是KPM算法做的事情，getIndexOf函数就是KMP算法的过程和实现。在本书KMP算法中有讲解。
5，将整数字符串转成整数值
题目：给定一个字符串str，如果str符合日常书写的整型形式，并且属于32位整数的范围，返回str所代表的整数值，否则返回0。
举例:str=”123”,返回123。str=”023”,因为023不符合平常书写习惯，所以返回0。str=”A13”，返回0；str=”2147483647”，返回2147483647。str=”2147483648”，因为溢出了，返回0。str=”-123”，返回-123。
本书提供一种解法如下：
1),若str不以”-“开头，也不以数字字符开头，例如，str==”A12”，返回false。
2),若str以”-“开头，但是str长度为1，即str=”-“，返回false。若str长度大于1，但是”-“的后面紧跟着”0”，例如，str=”-0”或”-012”，返回false。
3),若str以”0”开头，但是str的长度大于1，例如，str=”023”，返回false。
4),如果经过以上三个步骤都没有返回false，接下来检查str[1..n-1]是否都是数字字符，如果有一个不是数字字符，返回false。如果都是数字字符，说明符合日常书写，返回true。
具体参考下面isValid方法:

public static boolean isValid(char[] chas) {
		if (chas[0] != '-' && (chas[0] < '0' || chas[0] > '9')) {
			return false;
		}
		if (chas[0] == '-' && (chas.length == 1 || chas[1] == '0')) {
			return false;
		}
		if (chas[0] == '0' && chas.length > 1) {
			return false;
		}
		for (int i = 1; i < chas.length; i++) {
			if (chas[i] < '0' || chas[i] > '9') {
				return false;
			}
		}
		return true;
}

如果str不符合书写形式，返回0即可，若符合，则用如下方法进行转换过程。

public static int convert(String str) {
		if (str == null || str.equals("")) {
			return 0; // can not convert
		}
		char[] chas = str.toCharArray();
		if (!isValid(chas)) {
			return 0; // can not convert
		}
		boolean posi = chas[0] == '-' ? false : true;
		int minq = Integer.MIN_VALUE / 10;
		int minr = Integer.MIN_VALUE % 10;
		int res = 0;
		int cur = 0;
		for (int i = posi ? 0 : 1; i < chas.length; i++) {
			cur = '0' - chas[i];
			if ((res < minq) || (res == minq && cur < minr)) {
				return 0; // can not convert
			}
			res = res * 10 + cur;
		}
		if (posi && res == Integer.MIN_VALUE) {
			return 0; // can not convert
		}
		return posi ? -res : res;
}