字符串包含，java

╰+哭是因爲堅強的太久メ 2022-06-17 09:18 189阅读 0赞

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？

\+

为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)

比如，如果是下面两个字符串：

String 1：ABCD

String 2：BAD

答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。

如果是下面两个字符串：

String 1：ABCD

String 2：BCE

答案是false，因为字符串String2里的E字母不在字符串String1里。

同时，如果string1：ABCD，string 2：AA，同样返回true。

String 1：长度是m

String 2：长度是n

import java.util.ArrayList;
    import java.util.Scanner;
    
    //校验str2的字符是否都全在str1中
    public class Main {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		Scanner sc = new Scanner(System.in);
    		String str1 = sc.nextLine();
    		String str2 = sc.nextLine();
    		System.out.println("---------输出结果---------");
    		System.out.println(str1);
    		System.out.println(str2);
    		int hash = 0;
    		for (int i = 0; i < str1.length(); i++) {
    			hash = hash | (1 << (str1.charAt(i) - 'A'));
    		}
    
    		for (int j = 0; j < str2.length(); j++) {
    			if ((hash & (1 << (str2.charAt(j) - 'A'))) == 0) {
    				System.out.println("str2的字符不全在str1中");
    				return;
    			}
    		}
    		System.out.println("str2的字符全在str1中");
    	}//main
    }

ABCDEFGHIJAABCD
    ADCBG
    ---------输出结果---------
    ABCDEFGHIJAABCD
    ADCBG
    str2的字符全在str1中

空间复杂度为O(1)，时间复杂度还是O(n + m)。

其实也有第二种方法：

str2放在两个数组中b\[\],c\[\]，长度均是27，初始元素均是0

1.下标是1-26，对应字母A-Z，如果是'A'，则b\[1\],c\[1\]均+1，如果是'G',则b\[7\],c\[7\]均+1

2.遍历str1的字符，如果是'A'，则b\[1\]\+1,c\[1\]不变，如果是'G',则b\[7\]\+1,c\[7\]不变

3.遍历b\[\],c\[\]的对应下边的元素均不相同，则说明str2的字符全在str1中，返回true；如果对应下标的元素只要有一个相同，说明str2的字符不全在str1中,返回false

此时的时间复杂度是O(n + m)，空间复杂度是O(n)，没了那些位运算，多占了内存空间

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java判断字符串是否包含特定字符串

Java判断字符串是否包含特定字符串方法一，使用 contains 方法，返回boolean，包含返回True public static void m

柔光的暖阳◎/ 2024年03月31日 12:47/ 0 赞/ 69 阅读

相关 Java判断一个字符串是否包含某个字符串

开发过程中，有时会判断一个字符串是否包含某个字符串的操作，这里总结判断方法。方式一：contains()方法理解：contains() 方法用于判断字符串中是

心已赠人/ 2023年10月12日 14:32/ 0 赞/ 56 阅读

相关字符串包含 python

在Python中，字符串是一种常见的数据类型，它可以用来表示文本、数字等信息。字符串是由一系列字符组成的序列，可以使用单引号、双引号或三引号来表示。例如： str

古城微笑少年丶/ 2023年10月11日 21:18/ 0 赞/ 5 阅读

相关 JavaScript字符串包含

在任何编程语言中，检查字符串是否包含子字符串都是常见的任务。例如，假设您正在构建在线游戏。您可能需要检查用户名是否包含禁止使用的短语，以确保所有用户名都适合您的游戏。 Ja

我就是我/ 2023年10月04日 12:55/ 0 赞/ 18 阅读

相关 js包含字符串判断(js判断字符串包含某个字符串)

JS代码判断字符串中有多少汉字？本例的重点是正则表达式的应用步骤。(1)创建一个正则表达式变量“re”：(2)使用“re”的“test”方法，判断是否能榆索出符合条件的

╰半橙微兮°/ 2023年09月26日 14:46/ 0 赞/ 54 阅读

相关字符串包含，java

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？ \+ 为了简单起见，我们规定输入的字符串

╰+哭是因爲堅強的太久メ/ 2022年06月17日 09:18/ 0 赞/ 190 阅读

相关 java字符串包含问题

/ 用于判断用逗号分隔的字符串测试第一个字符串是否包含第二个字符串的内容若不包含则返回第一个不包含的内容

素颜马尾好姑娘i/ 2022年06月13日 01:22/ 0 赞/ 206 阅读

相关【java】java判断字符串A中是否包含字符串B

public static void main(String[] args) { String str="ABC_001";

àì夳堔傛蜴生んèń/ 2022年06月08日 13:50/ 0 赞/ 298 阅读

相关 java判断A字符串是否包含B字符串

判断是否包含字符串方法如下： public static void main(String[] args) { String

骑猪看日落/ 2022年05月26日 05:19/ 0 赞/ 458 阅读

相关 Java判断字符串是否包含数字

public static boolean isContainNumber(String company) \{ Pattern p = Patter

电玩女神/ 2022年03月19日 01:28/ 0 赞/ 449 阅读