字符串是否包含问题

柔光的暖阳◎ 2022-08-27 05:50 215阅读 0赞

## 题目描述 ##

假设这有两个分别由字母组成的字符串A另外字符串B，字符串B的字母数较字符串A少一些。什么方法能最快地查出字符串B所有字母是不是都在字符串A里？也就是说判断字符串B是不是字符串A的真子集（为了简化，姑且认为两个集合都不是空集，即字符串都不为空。）。

## 分析与解法 ##

解法一：暴力轮询

就是将B中的每一字符都和A中的字符做对比，思想简单此处就不再实现

解法二：普通排序

就是先对A 和 B做排序，然后对比B和A

/**
    	 * <p>
    	 * 普通排序的方式
    	 * </p>
    	 * @author zhangjunshuai
    	 * @date 2014-5-14 下午4:51:31
    	 */
    	public static void sortMy(){
    		String[] B = "a,w,d,f,e".split(",");
    		String[] A = "a,b,c,e,d,f,g,h,i,j".split(",");
    		Arrays.sort(A);
    		Arrays.sort(B);
    		
    		for(int pa=0,pb=0;pb<B.length;){
    			while((pa<A.length)&&((A[pa].toCharArray())[0]<(B[pb].toCharArray())[0])){//请注意此处的巧妙
    				++pa;
    			}
    			if(pa>=A.length||(A[pa].toCharArray())[0]>(B[pb].toCharArray())[0]){//此处是跳出循环
    				
    				break;
    			}
    			++pb;
    			
    		}
    		
    	}

解法三：计数比较法

因为字符总数都在一个固定范围内，小写字母是26个，所以我们可以创建一个长度为26的整数组，用来记录A中的字符出现的次数，为了便于B对比。我们又利用所有字符相对于初始字母‘a’的距离做数组下标，这样的话我们就可以用count\[1\] 记录在A中字母b出现的次数，以此类推。遍历完A之后，再让B和count数组比较，如果出现count中为0，而B中有的则B不完全包含在A中。

/**
    	 * <p>
    	 * 计数比较法
    	 * </p>
    	 * @author zhangjunshuai
    	 * @date 2014-5-14 下午5:22:41
    	 */
    	public static void countMy(){
    		String A = "abcekdjflti";
    		String B ="flt";
    		char[] a= A.toCharArray();
    		char[] b = B.toCharArray();
    		int[] count = new int[26];
    		for(char cc:a){
    			++count[cc-'a'];
    		}
    		for(char bb :b){
    			if(count[bb-'a']==0){
    				System.out.println("不在其中");
    				break;
    			}
    		}
    	}

PS：

本文是本人在学习[July算法][July]时候所做笔记，所有思想目前都来自此地址。

[July]: http://taop.marchtea.com/01.02.html