字符串专题算法练习

题目：判断字符串有无重复字符

判断一个字符串中是否有重复的字符。假设都是ASCII字符。

java代码示例：


public class 串内有无重复字符串 {
	public static void main(String[] args) {
		String s1 = "abcdsefg";
		String s2 = "adfasfad";
		System.out.println(check(s1));
		System.out.println(check(s2));
	}
	
	public static boolean check(String str) {
		//假设字符都是ASCII字符。
		int[] flag = new int [128];
		for(int i = 0; i < str.length(); i++) {
			int c = (int)str.charAt(i);
			if(flag[c] > 0) {
				return false;
			}
			flag[c]++;
		}
		return true;
	}
}

程序运行结果：

1 2	true false

题目：翻转字符串

请实现一个算法，翻转一个给定的字符串。

java代码示例：

public class 翻转字符串 {

	public static void main(String[] args) {
		String s1 = "abcdefg";
		System.out.println(reverseString(s1));
		System.out.println(reverse(s1));
	}
	//方法1：利用字符数组，逆序输出
	public static String reverseString(String str) {
		int len = str.length();
		char[] s = str.toCharArray();
		for(int i = 0; i < len; i++) {
			s[i] = str.charAt(len-i-1);
		}
		return new String(s);
	}
	//方法2：利用java自带API
	public static String reverse(String str) {
		StringBuilder sb = new StringBuilder(str);
		return sb.reverse().toString();
	}
}

程序运行结果：

1 2	gfedcba gfedcba

题目：变形词问题

给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

这里规定大小写为不同字符，且考虑字符串中的空格。

给定一个str1和一个str2，请返回一个boolean，代表两串是否重新排列后可相同。

保证两串的长度都小于5000.

解题思路：

方案1：首先判断两个字符串长度是否相等。如果不相等直接返货false。然后将两个字符串变为字符数组，将字符数组分别进行排序。比较两个字符数组是否相等。若相等返回true。否则返回false。时间复杂度：Nlgn

方案2：利用计数排序的思想。将第一个字符串的字符个数进行记录。然后利用第二个字符串的字符，将计数器减少，如果相等。计数器都为0，出现负数则返回false。

java代码示例：

import java.util.Arrays;

public class 变形词问题 {

	public static void main(String[] args) {
		String s1 = "abcdefg";
		String s2 = "defabcg";
		String s3 = "sdfksdc";
		System.out.println(isEquals(s1, s2));
		System.out.println(isEquals(s1, s3));
		System.out.println(isEq(s1, s2));
		System.out.println(isEq(s1, s3));
		
	}
	//方案1：通过字符数组排序后，比较是否相等
	public static boolean isEquals(String s1, String s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		if(len1 != len2)
			return false;
		char[] arr1 = s1.toCharArray();
		char[] arr2 = s2.toCharArray();
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		return Arrays.equals(arr1, arr2);
	}
	
	//方案2：假设都是ASCII字符，利用计数排序的思想来做
	public static boolean isEq(String s1, String s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		if(len1 != len2)
			return false;
		int[] count = new int[128];
		for(int i = 0; i < len1; i++) {
			char c = s1.charAt(i);
			count[c]++;
		}
		for(int i = 0; i < len2; i++) {
			char c = s2.charAt(i);
			count[c]--;
			if(count[c] < 0) {
				//如果为负数，则直接返回false
				return false;
			}
		}
		return true;
	}
}

程序运行结果：

true
false
true
false

题目：替换空格

请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度（小于等于1000），同时保证字符串由大小写英文字母组成。

输入：给定一个String str为原始的串，以及串的长度int len,返回替换后的str。

java代码示例：

public class 替换字符串中的空格 {

	public static void main(String[] args) {
		String s1 = "I am Mike";
		System.out.println(replaceSpace(s1, 15));
		System.out.println(replaceSpace("Are you OK00000000000000000000000".toCharArray(), 10));

	}
	//方案1：调用java API
	public static String replaceSpace(String s, int length) {
		return s.replace(" ", "%20");
	}
	//方案2：统计空格个数，扩展数组，倒退填写
	public static String replaceSpace(char[] str, int length) {
		int count = length;
		for(int i = 0; i < length; i++) {
			if(str[i] == ' ') {
				count+=2;
			}
		}
		
		int p1 = length-1;
		int p2 = count-1;
		while(p1 >= 0){
			if(str[p1] == ' ') {
				str[p2--] = '0';
				str[p2--] = '2';
				str[p2--] = '%';
			}else {
				str[p2--] = str[p1];
			}
			p1--;
		}
		return new String(str, 0, count);
	}

}

程序运行结果：

1 2	I%20am%20Mike Are%20you%20OK

题目：压缩字符串

利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。
比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。
若压缩后的字符串没有变短，则返回原先的字符串。
给定一个string iniString为待压缩的串(长度小于等于10000)，
保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。
测试样例
“aabcccccaaa”
返回：”a2b1c5a3”

java代码示例：

public class 压缩字符串 {

	public static void main(String[] args) {
		String s = zipString("aabbbccccddaaa");
		System.out.println(s);
        System.out.println(zipString("abc"));
	}
	
	public static String zipString(String str) {
		int count = 0; //记录前一个字符的次数
		char last = 0; //记录上一个字符
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);
			if(sb.length() == 0) {//处理第一个字符
				sb.append(c);
				last = c;
				count++;
			}else {
				if(c == last) { //和上一个字符相同
					count++;
				}else {//和上一个字符不同
					sb.append(count);
					sb.append(c);
					last = c;
					count = 1;//重置1
				}
			}
			//输出最后一个字符的重复次数
			if(i == str.length() - 1) {
				sb.append(count);
			}
		}
		//如果压缩后字符串没有变短，返回原来字符串
		if(sb.length() >= str.length()) {
			return str;
		}
		return sb.toString();
	}
}

程序运行结果：

1 2	a2b3c4d2a3 abc

题目：判断两字符串的字符集是否相等

实现一个算法，判断组成两字符集的字符是否相等。

java实现代码：

import java.util.HashMap;
import java.util.Map;

public class 判断字符集是否相等 {

	public static void main(String[] args) {
		System.out.println(isEq("adbcd", "adfabd"));
		System.out.println(isEq("adbcd", "abcdabc"));
	}
	
	public static boolean isEq(String s1, String s2) {
		Map<Character, Integer> map = new HashMap<>();
		for(int i = 0; i < s1.length(); i++) {
			char c = s1.charAt(i);
			if(map.get(c) == null) {
				map.put(c, 1);
			}
		}
		for(int i = 0; i < s2.length(); i++) {
			char c = s2.charAt(i);
			if(map.get(c) == null) {
				return false;
			}
		}
		return true;
	}
}

程序运行结果：

1 2	false true

题目：旋转词

给定两个字符串s1和s2，要求判定s2是否能被通过s1作循环一位得到的字符串包含。

例如：给定s1 = AABCD，s2 = CDAA，返回true。给定s1 = ABCD,s2 = ACBD,返回false。

java示例代码：

public class 旋转词 {

	public static void main(String[] args) {
		System.out.println(reverseWord("AABCD", "CDAA"));
		System.out.println(reverseWord("ABCD", "ACBD"));
		System.out.println(revWord("AABCD", "CDAA"));
		System.out.println(revWord("ABCD", "ACBD"));

	}
	//方法1：将两个s1拼接起来，判断s2是否在其中
	public static boolean reverseWord(String s1, String s2) {
		StringBuilder sb = new StringBuilder(s1).append(s1);
		return sb.toString().contains(s2);
	}
	//方法2：通过循环s1的字符，判断s2是否在其中
	public static boolean revWord(String s1, String s2) {
		StringBuilder sb = new StringBuilder(s1);
		for(int i = 0; i < s1.length(); i++) {
			sb.append(sb.charAt(0));
			sb.deleteCharAt(0);
			if(sb.toString().contains(s2)) {
				return true;
			}
			
		}
		return false;
	}

}

程序运行结果：

true
false
true
false

题目：将字符串按单词翻转

实现一个算法，将一个字符串按单词翻转。

例如：are you ok 翻转后为： ok you are

java代码示例：

public class 字符串按单词翻转 {
	public static void main(String[] args) {
		System.out.println(reverse("are you ok"));
	}

	public static String reverse(String str) {
		String s = reverseString(str);
		String[] words = s.split("\\s");
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < words.length; i++) {
			sb.append(reverseString(words[i]) + " ");
		}
		return sb.deleteCharAt(sb.length()-1).toString();
	}



	public static String reverseString(String str) {
		StringBuilder sb = new StringBuilder(str);
		return sb.reverse().toString();
	}
}

程序运行结果：

1	ok you are

题目：去掉字符串中连续出现的k次的0

public class 去掉字符串中连续出现的K次的0 {
	public static void main(String[] args) {
		System.out.println(deleteK0("1kjd0000sdl000sdalj0", 3));
		System.out.println(delK0("1kjd0000sdl000sdalj0", 3));
	}
	//方法1：利用java API
	public static String deleteK0(String str, int k) {
		String s = "0{" + k + "}";
		return str.replaceAll(s, "");
	}
	//方法2：扫描字符进行输出
	public static String delK0(String str, int k) {
		StringBuilder sb = new StringBuilder();
		int count = 0;
		for(int i = 0 ; i < str.length(); i++) {
			char c = str.charAt(i);
			if(c == '0') {
				count++;
				if(count == k) {
					count = 0;
				}
			}else {
				while (count > 0) {
					sb.append('0');
					count--;
				}
				sb.append(c);
			}
		}
		//添加末尾少于k个0
		while (count > 0) {
			sb.append('0');
			count--;
		}
		return sb.toString();
	}
}

程序运行结果：

1 2	1kjd0sdlsdalj0 1kjd0sdlsdalj0

题目：最短摘要的生成

给定一段产品的英文描述，包含M个英文单词，每个英文单词以空格分割，无其他标点符号；再给定N个英文单词关键词.目标是找出此产品描述中含N个关键词（每个关键词至少出现一次）的长度最短的子串，作为产品简介输出。

解题思路：

方法1：暴力破解。

双层循环，定住一个来寻找后面包含所有关键字的一段。记录此时的长度。循环执行，找到最短的子串。并记录最短子串的开始下标和结束下标。

方法2：尺取法。

通过两个指针，一个指左边第一个关键字，另一个指包含所有关键字的最短子串的最后一个。然后移动两个指针，找到最短子串。

java代码示例：

import java.util.Arrays;

public class 最短摘要生成 {

	public static void main(String[] args) {
		solve1(new String[]{"a", "b", "c", "seed", "h", "e", "f", "c", "c", "seed", "e", "f", "seed", "c"}, new String[]{"c", "e"});
		solve2(new String[]{"a", "b", "c", "seed", "c", "e", "f", "c", "c", "seed", "e", "f", "seed", "c"}, new String[]{"c", "e"});
		solve2(new String[]{"a", "b", "a", "a", "b", "c", "d", "h", "e", "f", "f"}, new String[]{"b", "c", "d"});
	}

	//方法1：原始暴力破解   时间复杂度 M^2*N
	private static void solve1(String[] w, String[] q) {
		int length = Integer.MAX_VALUE;
		int begin = -1;
		int end = -1;
		for (int i = 0; i < w.length; i++) {
			//求以i开头包含所有关键字的序列
			for (int j = i + 1; j < w.length; j++) {
				//如果全部关键词已经在seq中
				if (containsAll(q, w, i, j)) {
					//  判断当前这个序列是不是较短的序列
					// System.out.println(seq);
					if (j - i + 1 < length) {
						length = j - i + 1;
						begin = i;
						end = j;
					}
					break;
				}
			}
		}
		print(w, begin, end);
	}
	//判断关键词是否都在子串中
	private static boolean containsAll(String[] q, String[] w, int i, int j) {
		int[] falg = new int[q.length];
		for(int begin = i; begin <= j; begin++) {
			for(int k = 0; k < falg.length; k++) {
				if(w[begin].equals(q[k])) {
					falg[k] = 1;
				}
			}
		}
		for(int k = 0; k < falg.length; k++) {
			if(falg[k] != 1) {
				return false;
			}
		}
		return true;
	}
	//打印最短子串
	private static void print(String[] w, int begin, int end) {
		for(int i = begin; i <= end; i++) {
			System.out.print(w[i] + " ");
		}
		System.out.println();
	}
	//---------------------------------------------------------------------------------
	//方法2：尺取法
	private static void solve2(String[] w, String[] q) {
		//begin和end用于在找到更短的包含全部关键字的子数组时更新
		int begin = -1;
		int end = -1;
		int p2 = -1;//上一次囊括了所有关键的右边界
		int minLen = Integer.MAX_VALUE;
		//标记找到的关键字
		int[] keyFlag = new int[q.length];
		for(int i = 0; i < w.length; i++) {
			Arrays.fill(keyFlag, 0);
			//如果i位置是关键字，求以i开头包含所有关键字的序列
			String word = w[i];
			int index = indexOf(q, word);
			if(index == -1) {
				continue;
			}else {
				keyFlag[index] = 1;//标记一下
			}
			//确定右边界j
			int j;
			if(p2 != -1) {
				j = p2;
			}else {
				j = i + 1;
			}
			while(j < w.length) {
				String word2 = w[j];
				int index2 = indexOf(q, word2);
				if(index2 == -1 || keyFlag[index2] == 1) {
					//如果不是关键词或者该关键词已经找到，继续循环
					j++;
					continue;
				}else {//找到未发现的关键词
					keyFlag[index2] = 1;//标记
					//判断是否把所有关键词找到
					if(sum(keyFlag) == keyFlag.length) {
						p2 = j;
						if(j - i + 1 < minLen) {//更新minLen
							minLen = j - i + 1;
							begin = i;
							end = j;
						}
						break;
					}else {
						j++;
					}
				}
			}
		}
		print(w, begin, end);
	}

	private static int indexOf(String[] q, String word) {
		for(int i = 0; i < q.length; i++) {
			if(q[i].equals(word)) {
				return i;
			}
		}
		return -1;
	}

	private static int sum(int[] keyFlag) {
		int sum = 0;
		for(int i = 0; i < keyFlag.length; i++) {
			sum += keyFlag[i];
		}
		return sum;
	}
}

程序运行结果：

1
2
3

e f c 
c e 
b a a b c d

题目：字符串匹配之RabinKarp

有两个串，一个源串，一个模式。实现一个算法查看在源串中能匹配模式的下标。例如：源串“abcdec”,模式：“bcd” 则在源串中有bcd子串。并输出位置。

解题思路：

滚动hash法

对目标字符串按d进制求值,mod h 取余作为其hash

对源串,依次求出m个字符的hash,保存在数组中(滚动计算)

匹配时,只需比对目标串的hash值和预存的源串的hash值表

RabinKarp算法思想：可查看 http://blog.chinaunix.net/uid-26548237-id-3968132.html

java代码示例：

public class RabinKarp {
	
	final static long seed = 31;
	public static void main(String[] args) {
		String s1 = "abcdefgcde";
		String s2 = "cde";
		match(s2, s1);
	}
	 
	/**
	 * 
	 * @param p 模式
	 * @param s 源串
	 */
	public static void match(String p, String s) {
		long hash_p = hash(p);
		int pLen = p.length();
		for(int i = 0; i + pLen <= s.length(); i++) {
			long hash_i = hash(s.substring(i, i + pLen));
			if(hash_i == hash_p) {
				System.out.println("match:" + i);
			}
		}
	}
	public static long hash(String str) {
		long hash = 0;
		for(int i = 0; i < str.length(); i++) {
			hash = seed * hash + str.charAt(i);
		}
		return hash % Long.MAX_VALUE;
	}
}

程序运行结果：

1 2	match:2 match:7

算法改进：

对每n个字符做hash预处理，降低时间复杂度

public class RabinKarp1 {
	final static long seed = 31;
	public static void main(String[] args) {
		String s1 = "abcdefgcde";
		String s2 = "cde";
		match(s2, s1);
	}
	 
	/**
	 * @param p 模式
	 * @param s 源串
	 */
	public static void match(String p, String s) {
		long hash_p = hash(p);
		long[] hashOfs = hash(s, p.length());
		for(int i = 0; i < hashOfs.length; i++) {
			if(hashOfs[i] == hash_p) {
				System.out.println("match:" + i);
			}
		}
	}
	
	/**
	 * hash预处理，使时间复杂度变为O(M+N)
	 * @param str 字符串
	 * @param n 子串的长度
	 * @return 用滚动的方法求出s中长度为n的每个子串的hash，组成一个hash数组
	 */
	public static long[] hash(final String str, final int n) {
		long[] res = new long[str.length() - n + 1];
		//前m个字符的hash
		res[0] = hash(str.substring(0, n));
		for(int i = n; i < str.length(); i++) {
			char newChar = str.charAt(i);
			char oldChar = str.charAt(i - n);
			//前n个字符的hash*seed - 前n字符的第一字符 *seed的n次方
			long hash = (long) ((res[i - n] * seed - Math.pow(seed, n) * oldChar + newChar) % Long.MAX_VALUE);
			res[i - n + 1] = hash;
		}
		return res;
	}
	
	public static long hash(String str) {
		long hash = 0;
		for(int i = 0; i < str.length(); i++) {
			hash = seed * hash + str.charAt(i);
		}
		return hash % Long.MAX_VALUE;
	}
}

题目:字符串匹配之KMP

有字符str = “babababcbabababb”, 模式：s = “bababb”;

求出匹配位置。如果匹配返回匹配开始位置下标。否则返回-1.

java代码示例：

public class KMP字符串匹配 {

	public static void main(String[] args) {
		String str = "babababcbabababb";
		String s = "bababb";
		System.out.println(indexOf(str, s));
		System.out.println(indexOf1(str, s));
	}
	public static int indexOf(String str, String s) {
		int p = 0; //记录str开始比较的位置
		int p1 = 0;//记录str每次比较的表标
		int p2 = 0; //记录s的指针
		while(p <= str.length()-s.length()) {
			p1 = p;
			p2 = 0;
			while(p2 < s.length()) {
				if(s.charAt(p2) == str.charAt(p1)){
					if(p2 == s.length()-1) {
						return p;
					}
					p2++;
					p1++;
				}else {
					p++;
					break;
				}
			}
		}
		return -1;
	}

	public static int indexOf1(String str, String s) {
		if(str.length() < s.length()) return -1;
		if(s.length() == 0) return -1;

		int[] next = next(s);
		int i = 0; //str位置
		int j = 0; //s位置
		while(i < str.length()) {
			//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
			//j=-1，因为next[0]=-1,说明p的第一位和i这个位置无法匹配，这时i，j都增加1，i移位，j从0开始
			if(j == -1  || str.charAt(i) == s.charAt(j)) {
				i++;
				j++;
			}else {
				//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
		        //next[j]即为j所对应的next值
				j = next[j];
			}
			if(j == s.length()) { //匹配成功了
				return (i - j);
			}
		}
		return -1;
	}

	private static int[] next(String s) {
		//bababb
		/**
		 * 			b  -1  j = 0, k = -1
		 * 		   ba   0  j = 1, k = 0
		 * 		  bab   0  j = 2, k = 0;
		 *  	 baba   1  j = 3, k = 1;
		 *  	babab	2  j = 4, k = 2;
		 *     bababb	3  j = 5, k = 3;
 		 */
		int[] next = new int[s.length()];
		char[] p = s.toCharArray();
		next[0] = -1;
		if(s.length() == 1) {
			return next;
		}
		next[1] = 0;
		int j = 1;
		int k = next[j];//看看位置j的最长匹配在哪里
		while(j < s.length() - 1) {
			//要推出next[j+1],检查j和k位置上的关系即可
			if(k < 0 || p[j] == p[k]) {
				next[++j] = ++k;
			}else {
				k = next[k];
			}
		}
		return next;
	}
}

程序运行结果：

1
2

10
10