移动端电商网站,制作商城网站,网络服务费计入什么科目,上海外包seo题目
输入字符串s1和s2#xff0c;如何判断字符串s2中是否包含字符串s1的某个变位词#xff1f;如果字符串s2中包含字符串s1的某个变位词#xff0c;则字符串s1至少有一个变位词是字符串s2的子字符串。假设两个字符串中只包含英文小写字母。例如#xff0c;字符串s1为如何判断字符串s2中是否包含字符串s1的某个变位词如果字符串s2中包含字符串s1的某个变位词则字符串s1至少有一个变位词是字符串s2的子字符串。假设两个字符串中只包含英文小写字母。例如字符串s1为ac字符串s2为dgcaf由于字符串s2中包含字符串s1的变位词ca因此输出为true。如果字符串s1为ab字符串s2为dgcaf则输出为false。
分析
由变位词的定义可知变位词具有以下几个特点。首先一组变位词的长度一定相同其次组成变位词的字母集合一定相同并且每个字母出现的次数也相同。
由于这个题目强调字符串中只包含英文小写字母而英文小写字母的个数是确定的一共26个因此可以用数组模拟一个简单的哈希表。数组的下标0对应字母’a’它的值对应字母’a’出现的次数。数组的下标1对应字母’b’它的值对应字母’b’出现的次数。以此类推数组的下标25对应字母’z’它的值对应字母’z’出现的次数。
首先扫描字符串s1。每扫描到一个字符就找到它在哈希表中的位置并把它对应的值加1。如果字符串s1为ac那么在该哈希表中只有字母’a’和字母’c’对应的值是1其他值都是0这是因为只有这两个字母在字符串中各出现了1次。 遍历s2所有和s1相同长度的连续子字符串逐个扫描这个变位词中的字母并把字母在哈希表中对应的值减1。由于字符串s1的变位词和字符串s1包含相同的字母并且每个字母出现的次数也相同因此扫描完字符串s1的变位词之后哈希表中所有的值都是0。
解
public class Test {public static void main(String[] args) {boolean result checkInclusion(ac, dgcaf);System.out.println(result);}public static boolean checkInclusion(String s1, String s2) {if (s2.length() s1.length()) {return false;}int[] counts new int[26];// 注意同位词必须长度相等不能其中一个词多字母那不能算同位词for (int i 0; i s1.length(); i) {// 曾经减减过现在已经不包含那个字符了所以需要加加counts[s1.charAt(i) - a];counts[s2.charAt(i) - a]--;}if (areAllZero(counts)) {return true;}// 注意同位词必须长度相等不能其中一个词多字母那不能算同位词// i相当于第2个指针指向子字符串的最后一个字符。第1个指针指向下标为i-s1.length()的位置。两个指针之间的子字符串的长度一直是字符串s1的长度。for (int i s1.length(); i s2.length(); i) {counts[s2.charAt(i) - a]--;counts[s2.charAt(i - s1.length()) - a];if (areAllZero(counts)) {return true;}}return false;}private static boolean areAllZero(int[] counts) {for (int count : counts) {if (count ! 0) {return false;}}return true;}
}
