博客

题目描述：

输入两个字符串是s1和s2，判断s1中元素是否包含所有s2中元素？（每个元素只统计一次）

若s1为‘abcdabcd’ ，s2为‘abc’，则s1中字符包含s2中所有字符。输出true

若s1为‘abababa’ ，s2位‘abcd’，则s1中字符不包含s2中所有字符，输出false

思路：

1、遍历s1，将s1所有元素存入一个数组s3，设置标志位为1。

再遍历s2，检验s3中对应位置是否为1，若遍历结束，所有位置为1，说明s1包含s2所有元素，输出true，反之输出false。

j分析：对于“是否包含”的问题，基本上处理的方法都会与hashtable有关。

思路是把所有s1中出现的字符放在一个长度为128的字符数组s3里，比如，”ABBC” 就是s3= {1, 1, 1, 0, … , 0}，

然后对于每个在s2字符串中出现的字符，在s3里设置为1。只要遇到s3[ s2[i] – ‘a’ ] = 0, 返回 false。

C++ 代码实现：

/*
功能：检验s1是否包含s2中所有元素
若包含，输出true。否则输出false
s1 、s2为输入字符串
s3 哈希数组
*/

#include<iostream>
#include<string>
using namespace std;

int main() {
	string s1, s2;
	while ( cin >> s1 ) {
		cin >> s2;
		int s3[128] = { 0 };           //定义哈希数组，并初始化
		if ( !s1.empty() ) {
			for ( int i = 0; i < s1.size() ; i++) {    
				s3[ s1.at(i) - 'a'] = 1;                //  将s1中元素记录到s3
			}
		}
		if ( !s2.empty() ) {
			for (int i = 0; i < s2.length() ; i++) {
				if ( s3[ s2.at(i) - 'a' ] != 1) {         
					cout << false << endl;
				    break;
				}
				if ( i == s2.length() - 1 && s3[s2.at(i) - 'a'] == 1) {
					cout << true << endl;
				}
			}
		}
	}
	system("pause");
}