字符串相关习题

发表于 | 分类于

判断两个字符串是否互为变形词

题目
  给定两个字符串str1和str2，如果str1和str2中出现的字符种类一样且每种字符出现的次数也一样，那么str1和str2互为变形词。请实现函数判断两个字符串是否互为变形词。

举例
　　str1=”396”,str2=”936”,返回true。
　　str1=”396”,str2=”3691”,返回false

思路

  1. 如果字符串str1和str2的长度不一样，直接返回
  2. 如果长度相同，假设出现的字符编码值在0～255之间，则可以申请一个整型数组arr，长度为256，arr[a]=b代表字符编码为a的字符出现了b次，初始时arr[0~255]的值都为0，然后遍历字符串str1，计算每种字符出现的次数。比如，遍历的字符为‘a’，其编码值为97，咋arr[97]++，同理遍历字符串str2，arr[97]–，如果减少之后的值小于0，返回false，如果遍历完str2，arr中的值也没有出现，则返回false。
  3. 如果字符的种类比较多，可以用哈希表代替整型数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Deformation_01 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(Deformation("121", "213"));
	}

	private static boolean Deformation(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;
	}
}

判断两个字符串是否互为旋转词

题目
  对于一个字符串str，把前面任意部分挪到后面形成的字符串叫作str的旋转词。比如str=”1234”，其旋转词有”2341”、”3412”、”4123”、”1234”。给定两个字符串a和b，判断a和b是否互为旋转词。

思路

  1. 如果字符串str1和str2的长度不一样，直接返回
  2. 如果长度相同，生成str1+str1的大字符串
  3. 用KMP算法判断大字符串中是否含有str2

代码实现

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class IsRotation_01 {
	public static void main(String[] args) {
		String str1 = "1234";
		String str2 = "2341";
		System.out.println(isRotation(str1, str2));
	}

	private static boolean isRotation(String str1, String str2) {
		if (str1 == null || str2 == null || str1.length() != str2.length()) {
			return false;
		}
		String str = str1 + str1;
		if (str.contains(str2)) {
			return true;
		}
		return false;
	}
}

给定一个字符串，按单词将该字符串逆序

题目
  对于一个字符串str，按单词将该字符串逆序。

举例
　　“pig loves dog” 逆序成 “dog loves pig”
　　“i’m a student.” 逆序成 “student. a i’m” 　　

思路

  1. 如果字符串str1和str2的长度不一样，直接返回
  2. 如果长度相同，生成str1+str1的大字符串
  3. 用KMP算法判断大字符串中是否含有str2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ReverseStr_01 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str = "i'm a student.";
		reverseStr(str);
	}
	private static void reverseStr(String str) {
		if (str.length() == 0) {
			return;
		}
		String[] tmp = str.split(" ");
		StringBuilder builder = new StringBuilder();
		for (int i = tmp.length - 1; i >= 0; i--) {
			builder.append(tmp[i] + " ");
		}
		System.out.println(builder.toString());
	}
}

给定一个字符串，和一个整数i，i代表str中的位置，将str[0…1]移到右侧，str[i+1…N-1]移到左侧。

举例
　　str = “ABCDE”，i=2。 将str调整为”DEABC”。
　　要求，时间复杂度为O(N),额外空间复杂度为O(1)。 　　

思路

  1. 将str[0…i]部分的字符逆序
    A B C D E
    C B A D E

  2. 将str[i+1 ~ N-1]部分的字符逆序
    A B C D E
    C B A E D

  3. 将str整体的字符逆序
    C B A D E
    D E A B C

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    public class reverseStr {
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
            // reverseStr_02("ABCDE", 3);
    		System.out.println(reverseStr_02("ABCDE", 2));
    	}

    	private static String reverseStr_02(String str, int i) {
    		if (str.length() == 0 || str == null || i > str.length()) {
    			return str;
    		}
    		String tmp = (dealStr(str.substring(0, i)) + dealStr(str.substring(i, str.length())));
    		return dealStr(tmp);
    	}
    	private static String dealStr(String str) {
    		char[] tmp = str.toCharArray();
    		StringBuilder builder = new StringBuilder();
    		for (int j = 0; j <= tmp.length / 2; j++) {
    			char c = tmp[j];
    			tmp[j] = tmp[tmp.length - j - 1];
    			tmp[tmp.length - j - 1] = c;
    		}
    		for (int i = 0; i < tmp.length; i++) {
    			builder.append(tmp[i]);
    		}
    		return builder.toString();
    	}
    }