首页 > 试题广场 >

确定两串乱序同构

[编程题]确定两串乱序同构

热度指数：47291 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定string stringA和string stringB，编写程序确认两字符串包含的字符是否完全相同，注意大小写为不同字符，且考虑字符串中的空格，返回一个bool，代表两串是否由一样的字符组成。保证两串的长度都小于等于5000。

示例1

输入

"This is nowcoder","is This nowcoder"

输出

true

示例2

输入

"Here you are","Are you here"

输出

false

算法知识视频讲解

推荐

Ron

/*同理，字符按ASCII大小在数组中存放对应字符出现个数，若两个字符串中各字符出现字数相同，则返回true，反之false*/
import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
    	int lenA = stringA.length();
    	int lenB = stringB.length();
    	if(lenA != lenB){
    		return false;
    	}
    	int[] strA = new int[256];
    	int[] strB = new int[256];
    	for(int i = 0; i < lenA; i++){
    		strA[stringA.charAt(i)]++;
    		strB[stringB.charAt(i)]++;
    	}
    	for(int i = 0;i<256;i++){
    		if(strA[i]!=strB[i]){
    			return false;
    		}
    	}
    	return true;
    }
}

编辑于 2015-10-04 19:00:13 回复(34)

Java

牛客774239950号

直接把字符转ASCLL加起来，两个字符串如果最后结果一样就是相同。

发表于 2022-08-24 09:43:15 回复(1)

Java

wanbf

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        if(stringA == null || stringB == null || stringA.length()!=stringB.length()) return false;
        
        HashMap<Character,Integer> map = new  HashMap<Character,Integer>();
        for(int i=0;i<stringA.length();i++){
            if(!map.containsKey(stringA.charAt(i))){
                map.put(stringA.charAt(i),1);
            }else map.put(stringA.charAt(i),map.get(stringA.charAt(i))+1);
        }
        for(int i=0;i<stringA.length();i++){
            if(!map.containsKey(stringB.charAt(i)) || map.get(stringB.charAt(i))==0){
                return false;
            }else map.put(stringB.charAt(i),map.get(stringB.charAt(i))-1);
        }
        return true;
    }
}

发表于 2022-01-17 00:09:22 回复(0)

Java

双加贝

package june.code.byhehe.book.GoldBook;

import java.util.Arrays;
import java.util.Comparator;

public class CM3MakeSure {
    public static void main(String[] args) {
        CM3 cm3 = new CM3();
        String a = "This is nowcoder";
        String b = "is This nowcoder";
        System.out.println(cm3.checkSam(a, b));
        System.out.println(cm3.checkSam2(a,b));
        System.out.println(cm3.checkSam3(a,b));
    }
}

class CM3{
    // 考虑使用 256 长度进行判断 或者使用 map 进行判断
    // 空间：O(n)   时间：O(n)
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        // 考虑判断长度
        if(stringA.length() != stringB.length())
            return false;

        int[] map1 = new int[256];
        int[] map2 = new int[256];

        for (int i = 0; i < stringA.length(); i++) {
            char c = stringA.charAt(i);
            char c2 = stringB.charAt(i);
            map1[c]++;
            map2[c2]++;
        }

        for (int i = 0; i < 256; i++) {
            if(map1[i]!=map2[i])
                return false;
        }
        return true;
    }
    // 重排单词 进行比较
    // 空间：O(n)   时间：O(nlogn)
    public boolean checkSam2(String stringA, String stringB) {
        String[] splitA = stringA.split(" ");
        String[] splitB = stringB.split(" ");
        if(splitA.length!=splitB.length)
            return false;

        Arrays.sort(splitA, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });

        Arrays.sort(splitB, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });

        for (int i = 0; i < splitA.length; i++) {
            if(!splitA[i].equals(splitB[i]))
                return false;
        }
        return true;
    }

    // 还有一种方法 基于上面的重排单词 ， 由于题目并未严格要求 以单词为基准， 
      所以我们可以重排所有字符进行比较
    // 空间：O(n)  时间：O(n)
    public boolean checkSam3(String stringA, String stringB) {
        // 需要借助 char 数组
        if(stringA.length()!=stringB.length())
            return false;

        char[] chars1 = stringA.toCharArray();
        char[] chars2 = stringB.toCharArray();

        Arrays.sort(chars1);
        Arrays.sort(chars2);
        // 直接调用 Arrays.equals 方法来进行比较
        return Arrays.equals(chars1, chars2);

        /*
        // 没必要 再写 其实 Arrays 里面源码就是这样写的
        for (int i=0; i<length; i++)
            if (a[i] != a2[i])
                return false;
         */
    }
}

发表于 2020-09-24 10:21:00 回复(0)

Java

也许不一样

private boolean equals(String a,String b){
        if(a==b){
            return true;
        }
        if(a==null||b==null){
            return false;
        }
        if(a.length()!=b.length()){
            return false;
        }
        int[] array=new int[256];
        for(int i=0;i<a.length();i++){
            array[a.charAt(i)]++;
            array[b.charAt(i)]--;
        }
        for(int i=0;i<array.length;i++){
            if(array[i]!=0){
                return false;
            }
        }
        return true;
    }

发表于 2020-07-20 10:59:04 回复(0)

Java

冰凤恋雪

苦思冥想想不出怎么做，看了讨论区知道可以通过字符出现的次数做判断

于是想到曾用过一个util可以判断一个字符串每个字符出现的次数，于是改造一番拿来用

以下正确答案主要代码：

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        if(stringA.length()!=stringB.length()){return false;}
        Map<Character,Integer> mapa = statCharsFrequency(stringA);
        Map<Character,Integer> mapb = statCharsFrequency(stringB);
        // 通过遍历key判断该key出现的次数是否相同
        for(Character key:mapa.keySet()) {
            System.out.println("Key: "+key+" Value: "+mapa.get(key));
            if (!mapa.get(key).equals(mapb.get(key))) {
                return false;
            }
        }
        return true;
    }
    public static Map<Character,Integer> statCharsFrequency(String string){
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        char[] arr = string.toCharArray();
        for (char ch : arr) {
            if (map.containsKey(ch)) {
                Integer old = map.get(ch);
                map.put(ch, old + 1);
            } else {
                map.put(ch,1);
            }
        }
        return map;
    }
}

发表于 2019-11-11 17:16:03 回复(0)

Java

来过2

import java.util.*;

//我是一直咸鱼。。。。
public class Same {
public boolean checkSam(String stringA, String stringB) {
// write code here
if(stringA.length() != stringB.length()) return false;
int tmp = 0;
for(int i = 0;i < stringA.length();i++){
tmp += stringA.charAt(i) - stringB.charAt(i);
}
if(tmp != 0) return false;
return true;
}
}

发表于 2019-02-26 18:52:03 回复(0)

Java

巧天工

   代码：
       int lengthA = stringA.length();
    int lengthB = stringA.length();
    if (lengthA != lengthB) return false;

    HashMap<Character, Integer> hmA = new HashMap<Character, Integer>();
    char c;
    for (int i = 0; i < lengthA; i++) {
      c = stringA.charAt(i);
      if (!hmA.containsKey(c)) {
        hmA.put(c, 1);
      } else {
        hmA.put(c, hmA.get(c) + 1);
      }
    }
    
    HashMap<Character, Integer> hmB = new HashMap<Character, Integer>();
    for (int i = 0; i < lengthB; i++) {
      c = stringB.charAt(i);
      if (!hmB.containsKey(c)) {
        hmB.put(c, 1);
      } else {
        hmB.put(c, hmB.get(c) + 1);
      }
    }
    return hmA.equals(hmB);

思路：

 统计每个字符和出现的次数，存入HashMap，比较HashMap是否相同。

发表于 2018-11-04 13:36:24 回复(0)

Java

yo蝶

import java.util.*;

public class Same {
public boolean checkSam(String stringA, String stringB){
if((stringA==null)||(stringB==null)||!(stringA.length()==stringB.length())) return false;
char[] arra = stringA.toCharArray();
HashMap<Character,Integer> hm = new HashMap<Character,Integer>();
for(char c : arra){
if(!hm.containsKey(c)){
hm.put(c, 1);
}else{
hm.put(c,hm.get(c)+1);
}
}

char[] arrb = stringB.toCharArray();
for(char b : arrb){
if(hm.containsKey(b)){
hm.put(b,hm.get(b)-1);
if(hm.get(b)==0)
hm.remove(b);
}
}
return hm.isEmpty();
}

}

先判断字符串是否为空是否不相等，再使用hashmap来记录字符出现次数，解法应该还能更简单。

发表于 2018-02-09 14:01:35 回复(0)

Java

哈哈哈啊嗝

    public boolean checkSam(String stringA, String stringB) {         boolean res = true;         for(int i = 0; i<stringA.length() ; i++) {                          for(int j = 0 ; j<stringB.length() ; j++)
            {
                if(!stringB.contains(stringA.substring(i, i+1)) ) {
                    res = false;
                    break;
                }
            }
        }         return res;
    }


用python一行代码就是实现了，人生苦短啊！

发表于 2018-01-23 20:35:26 回复(0)

Java

TaurusXi

public boolean checkSam(String stringA, String stringB) { // write code here  if (stringA.length() != stringB.length()){ return false;  } if (stringA.equals(stringB)){ return true;  } char[] charsA = stringA.toCharArray();  Arrays.sort(charsA);   char[] charsB = stringB.toCharArray();  Arrays.sort(charsB);   return Arrays.equals(charsA, charsB); }

发表于 2017-08-21 21:54:38 回复(0)

Java

壹步之【遥】！

* 思想很简单要返回TRUE 必须满足:

* 1. 两个字符串长度相等

* 2. 两字符串中字符以及字符对应出现次数要分别相等

* 采用哈希表 key>a串的字符 value>对应出现的次数遍历一遍得到map

* 再遍历b串如果当前字符在map不存在则false

* 存在的话把对应数量减一数量减到0 则删除map内的对应映射关系

* 遍历过后如果a b 匹配则 map必为空

* map非空说明不匹配返回FALSE

import java.util.*;

public class Same {

public boolean checkSam(String a, String b) {

if(a==null||b==null||a.length()==0||b.length()==0||

a.length()!=b.length()){

return false;

}

HashMap<Character,Integer> map = new HashMap<>();

char []arra = a.toCharArray();

char []arrb = b.toCharArray();

char c = 'c';

int count = 0;

for(int i=0;i<arra.length;i++){

c = arra[i];

if(!map.containsKey(c)){

map.put(c,1);

}else if(map.containsKey(c)){

count = map.get(c);

map.put(c,count+1);

}

for(int i=0;i<arrb.length;i++){

c = arrb[i];

if(!map.containsKey(c)){

return false;

}else if(map.containsKey(c)){

count = map.get(c);

if(count-1==0){

map.remove(c);

continue;

}

map.put(c,count-1);

}

return map.isEmpty();

}

发表于 2017-08-19 19:06:08 回复(0)

Java

欢乐🐎

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // 长度不同肯定不行
    	if (stringA.length()!=stringB.length()){
    		return false;
    	}
    	int len = stringA.length();
    	int res = 0;
        // 长度相同就直接遍历取异或
    	for (int i=0; i<len; i++){
    		char a = stringA.charAt(i);
    		char b = stringB.charAt(i);
    		res = res^(int)a;
    		res = res^(int)b;
    	}
        // 值为0表示可以重排实现
    	if (res==0)	return true;
    	else {
			return false;
		}
    }
}

发表于 2017-06-22 16:41:12 回复(1)

Java

村长，那人偷牛！

 //方法一：o(n)按位于 这方法有误，虽然能AC
public boolean checkSam(String stringA, String stringB) {
        if(stringA==null&&stringB==null) return true;
        if(stringA==null||stringB==null) return false;
        if(stringA.length()!=stringB.length()) return false;
        StringBuffer sbA=new StringBuffer(stringA);
        StringBuffer sbB=new StringBuffer(stringB);
        int result=0;
        for(int i=0;i<stringA.length();i++){
            result=sbA.charAt(i)^sbB.charAt(i)^result;
        }
        if(result!=0) return false;
        return true;
    }
//方法二，基于hash表，
 public boolean checkSam(String stringA, String stringB) {
        if(stringA==null&&stringB==null) return true;
        if(stringA==null||stringB==null) return false;
        if(stringA.length()!=stringB.length()) return false;
       	HashMap<Character,Integer> mapA=new HashMap<Character,Integer>();
        HashMap<Character,Integer> mapB=new HashMap<Character,Integer>();
        for(int i=0;i<stringA.length();i++){
           mapA.put(stringA.charAt(i),mapA.containsKey(stringA.charAt(i))?mapA.get(stringA.charAt(i))+1:0);
           mapB.put(stringB.charAt(i),mapB.containsKey(stringB.charAt(i))?mapB.get(stringB.charAt(i))+1:0);
        }
        for(char ch:mapA.keySet()) if(mapA.get(ch)!=mapB.get(ch)) return false;
        return true;
    }
//方法三，定义两个数组，原理类似hash表
 public boolean checkSam(String stringA, String stringB) {
        if(stringA==null&&stringB==null) return true;
        if(stringA==null||stringB==null) return false;
        if(stringA.length()!=stringB.length()) return false;
       	int[] arrayA=new int[256];
        int[] arrayB=new int[256];
        HashMap<Character,Integer> mapB=new HashMap<Character,Integer>();
        for(int i=0;i<stringA.length();i++){
            arrayA[stringA.charAt(i)]++;
            arrayB[stringB.charAt(i)]++;
        }
       for(int i=0;i<arrayA.length;i++) if(arrayA[i]!=arrayB[i]) return false;
       return true;
    }

编辑于 2017-05-10 14:41:44 回复(1)

Java

双子座

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        char[] chars1 = stringA.toCharArray();
        char[] chars2 = stringB.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        return new String(chars1).equals(new String(chars2));
    }
}

发表于 2017-04-27 17:25:50 回复(0)

Java

jumin17

创建两个长度为256的数组，分别记录数据的个数，然后进行统计，最后比较这两个数组

发表于 2017-04-23 22:58:41 回复(0)

Java

MaiFree

public boolean checkSam(String stringA, String stringB) {

if(stringA.length()!=stringB.length())

return false;

char sb='a';

for(int i=0;i<stringA.length();i++){

sb^=stringA.charAt(i);

sb^=stringB.charAt(i);

}

if(sb=='a')

return true;

else

return false;

    }
On时间度最短的- -

发表于 2017-04-17 17:16:02 回复(0)

Java

大鱼BigFish

public class Same {

public boolean checkSam(String stringA,String stringB)

{

int a,b;

a=stringA.length();

b=stringB.length();

if(a!=b)

return false;

char[] A=new char[a];

char[] B=new char[a];

for(int i=0;i<a;i++)

{

A[i]=stringA.charAt(i);

B[i]=stringB.charAt(i);

}

Arrays.sort(A);

Arrays.sort(B);

for(int i=0;i<a;i++)

{

if(A[i]!=B[i]) //排序后逐位比较字母，会比以ASCII码做下标存储字母个数然后比较费时

return false;

}

return true;

}

发表于 2017-04-11 21:49:49 回复(0)

Java

Holiday_12138

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        if(stringA.length()!=stringB.length())
            return false;
        HashMap<Character,Integer> map=new HashMap<Character,Integer>();
        for(int i=0;i<stringA.length();i++){
            if(map.containsKey(stringA.charAt(i)))
                map.put(stringA.charAt(i),map.get(stringA.charAt(i))+1);
            else
                map.put(stringA.charAt(i),1);
        }
        for(int i=0;i<stringB.length();i++){
            if(map.containsKey(stringB.charAt(i))){
                map.put(stringB.charAt(i),map.get(stringB.charAt(i))-1);
            	if(map.get(stringB.charAt(i))==0)
                	map.remove(stringB.charAt(i));  
            }
            else
                return false;
    	}
        return true;
    }
}

发表于 2017-04-03 16:59:34 回复(0)

Java

小风筝0010

本人编程渣渣，来谈一下这道题的编程感受。

首先，我觉得题目没说清楚的地方，进行排序的是字符串中的单词，还是每个字符。一开始我以为是单词，于是没通过。

后来根据原来的思路，改进下，通过：

解法一：

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
           //特殊输入判断
        if (stringA == null || stringB == null ||stringA.length() != stringB.length()) {
            return  false;
        }
        //思路：1. 将stringA转换为数组，保存字符串中的每个字符。
        //2. 然后将每个字符加到list，
        //3. 同理，转换字符串stringB为数组
        //4. 遍历数组b中的每个字符，如果list中存在，那么，移除。
        //5. 如果list为空，那么返回true。
        ArrayList<Character> list = new ArrayList<>();
        char[] a = stringA.toCharArray();
        char[] b = stringB.toCharArray();
        for (int i = 0; i < a.length; i ++) {
            list.add(a[i]);
        }
        for (int i = 0; i < b.length; i ++) {
            if (list.contains(b[i])) {
                list.remove(list.indexOf(b[i]));
            }
        }
        return list.isEmpty();
    }
}

解法二：

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
             //统计stringA和strngB各字符出现的次数，如果每个字符出现的次数
        // 相同，则返回true.各字符以ASCII码表示
        //特殊输入判断
        if (stringA == null || stringB == null ||stringA.length() != stringB.length()) {
            return  false;
        }
        int[] strA = new int[256];
        int[] strB = new int[256];
        for (int i = 0; i < stringA.length(); i ++) {
            strA[stringA.charAt(i)] ++;
            strB[stringB.charAt(i)] ++;
        }
        for (int i = 0; i < 256; i ++) {
            if (strA[i] != strB[i]) return false;
        }
        return true;
    }
}

解法三：

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
          //特殊输入判断
        if (stringA == null || stringB == null ||stringA.length() != stringB.length()) {
            return  false;
        }
        char[] a1 = stringA.toCharArray();
        char[] a2 = stringB.toCharArray();
        Arrays.sort(a1);
        Arrays.sort(a2);
        return Arrays.equals(a1, a2);
    }
}

编辑于 2017-03-14 20:23:59 回复(0)

Java

牛客495452号

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        HashMap<Character, Integer> hashMapA= new HashMap<Character, Integer>();
            HashMap<Character, Integer> hashMapB= new HashMap<Character, Integer>();
            if (stringA.length() != stringB.length())
                return false;
            for(int i=0; i<stringA.length();i++) {
                hashMapA.put(stringA.charAt(i), 0);
            }
            for(int i=0; i<stringA.length();i++) {
                int j= hashMapA.get(stringA.charAt(i));
                hashMapA.put(stringA.charAt(i), j++);
            }
            for(int i=0; i<stringB.length();i++) {
                hashMapB.put(stringB.charAt(i), 0);
            }
            for(int i=0; i<stringB.length();i++) {
                int j= hashMapB.get(stringB.charAt(i));
                hashMapB.put(stringB.charAt(i), j++);
            }
            /*for (Map.Entry<Character, Integer> entry : hashMapA.entrySet()) {
                entry.getKey();
                entry.getValue();
            }*/
            for(int i=0; i<stringA.length();i++) {
                if (hashMapA.get(stringA.charAt(i))!= hashMapB.get(stringA.charAt(i)))
                    return false;
            }
            return true;
        }
    }
O(n)的时间复杂度

发表于 2017-03-02 18:20:51 回复(0)