IT企业面试题（java描述）-字符串包含（1）

题目：

给出长字符串和短字符串，检查短字符串里面的字符是否都在长字符串里面出现。

例子：

长字符串：“abcdef”

短字符串：“abc” "abb" “ae”

检查结果是：true，true，false

1.思路

（1）暴力解法

使用双循环轮询，但是这种算法的缺点是时间复杂度为O（m*n）

（2）使用HashMap的特性

利用HashMap的特性，首先把长字符串按字符放入map里面，计算map的size，然后再把短字符串按字符放进去，在计算map的size，对比两次的结果，如果是等于，就是都在里面，如果是大于，就是有不在的字符

这种算法的空间复杂度是O（m+n）

2.代码

（1）暴力解法代码：

package com.ray.interview.ch01.topic_1_2;

/**
 * 检查字符串b里面的字符是否在a里面都出现过
 * 
 * @author raylee
 * @date 2016-02-16
 * @version 1.0
 */
public class ContainString_1 {

	public static boolean isContain(String a, String b) {
		boolean isContainStr = true;
		char[] charA_array = a.toCharArray();
		char[] charB_array = b.toCharArray();
		for (int i = 0; i < charB_array.length; i++) {
			boolean isContainChar = false;
			for (int j = 0; (j < charA_array.length); j++) {
				if (charA_array[j] == charB_array[i]) {
					isContainChar = true;
					break;
				}
			}
			if (!isContainChar) {
				isContainStr = false;
				break;
			}
		}
		return isContainStr;
	}

	public static void main(String[] args) {
		String a = "abc", b = "abb";
		System.out.println(isContain(a, b));
		String c = "abc", d = "aaa";
		System.out.println(isContain(c, d));
		String e = "cba", f = "ea";
		System.out.println(isContain(e, f));
	}

}

true
true
false

（2）使用HashMap的代码：

package com.ray.interview.ch01.topic_1_2;

import java.util.HashMap;

/**
 * 检查字符串b里面的字符是否在a里面都出现过
 * 
 * @author raylee
 * @date 2016-02-16
 * @version 1.0
 */
public class ContainString_2 {

	public static boolean isContain(String a, String b) {
		boolean isContainStr = true;
		char[] charA_array = a.toCharArray();
		char[] charB_array = b.toCharArray();
		HashMap<Character, Character> map = new HashMap<>();
		for (int i = 0; i < charA_array.length; i++) {
			map.put(charA_array[i], charA_array[i]);
		}
		int sizeA = map.keySet().size();
		for (int i = 0; i < charB_array.length; i++) {
			map.put(charB_array[i], charB_array[i]);
		}
		int sizeB = map.keySet().size();
		if (sizeA < sizeB) {
			isContainStr = false;
		}
		return isContainStr;
	}

	public static void main(String[] args) {
		String a = "abc", b = "abb";
		System.out.println(isContain(a, b));
		String c = "abc", d = "aaa";
		System.out.println(isContain(c, d));
		String e = "cba", f = "ea";
		System.out.println(isContain(e, f));
	}

}

true
true
false

总结：这一章节主要介绍了字符串包含面试题的两种思路和代码。

IT企业面试题（java描述）-字符串包含（1）

原文：http://blog.csdn.net/raylee2007/article/details/50675896