首页 > 试题广场 > 确定两串乱序同构
[编程题]确定两串乱序同构
  • 热度指数:43998 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。这里规定大小写为不同字符,且考虑字符串中的空格。

给定一个string stringA和一个string stringB,请返回一个bool,代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。

测试样例:
"This is nowcoder","is This nowcoder"
返回:true
"Here you are","Are you here"
返回:false
推荐
Ron头像 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 回复(33)
import java.util.*;
//这个题坑的地方在于:不是各个单词重排,是所有单个字符可以重排!!!
public class Same {
    public static boolean checkSam(String stringA, String stringB) {
    	char[] c1 = stringA.toCharArray();
    	char[] c2 = stringB.toCharArray();
    	Arrays.sort(c1);
    	Arrays.sort(c2);
    	return Arrays.equals(c1, c2);	//注意使用Arrays.equals(c1, c2)而不是c1.equals(c2):如果两个数组以相同顺序包含相同的元素,则两个数组是相等的
    }
}

发表于 2016-07-04 11:10:45 回复(9)
//先判断大小是否相同。不同则直接返回false
//相同,则使用两个大小为256的散列表,通过一次遍历找到每一个字符出现的次数
//再遍历hashTable来判断每一个字符出现的次数是否相同。一旦某个字符出现不同次数
//直接返回false  全部相同返回true

class Same {
public:
    bool checkSam(string stringA, string stringB) {
        // write code here
        int sizA = stringA.size();
        int sizB = stringB.size();
        
        if(sizA != sizB) return false;
        
        char A[256] = {0};
        char B[256] = {0};
        for(int i = 0; i < sizA; i++){
            A[stringA[i]]++;
            B[stringB[i]]++;
        }
        
        for(int i = 0; i < 256; i++){
            if(A[i] != B[i]) return false;
        }
        
        return true;
    }
};

发表于 2016-04-27 15:00:29 回复(14)
class Same {
public:
    bool checkSam(string stringA, string stringB) {
        // write code here
        char count[256]={0};
      	if(stringA.size()!=stringB.size()) return false;
        
        for(int i=0;i<stringA.size();i++)
        {
        	count[stringA[i]]++;
                count[stringB[i]]--;
        }
        for(int i=0;i<256;i++)
            if(count[i]!=0)
            	return false;
        return true;
    }
};

发表于 2015-09-14 19:04:58 回复(16)
L0L头像 L0L
//有点无耻额,直接用的sort函数,虽然简洁,复杂度却是O(nlogn);
//正规的做法,应该是hash,用256的元素记录每个字符出现的次数
//再进行比较,扫描一遍,比较一遍,复杂度只要O(n).
class Same {
public:
    bool checkSam(string stringA, string stringB) {
       
        sort(stringA.begin(),stringA.end());
        sort(stringB.begin(),stringB.end());
        return stringA.compare(stringB)==0;
    }
};

发表于 2015-09-09 15:22:55 回复(4)

Life is short, I use python.

Only one line:

return set(stringA)==set(stringB)
发表于 2017-10-01 20:10:30 回复(5)
# -*- coding:utf-8 -*-
class Same:
    def checkSam(self, stringA, stringB):
        if len(stringA) != len(stringB):
            return False
        
        char_setA = [0] * 256
        char_setB = [0] * 256
        for a,b in zip(stringA, stringB):
            char_setA[ord(a)] += 1
            char_setB[ord(b)] += 1
        
        return char_setA == char_setB
发表于 2016-08-13 09:28:29 回复(0)
import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        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.remove(b);
			}
		}
		return hm.isEmpty();
    }
}

发表于 2016-08-05 21:43:17 回复(3)
居然没有人用异或???
import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        if(stringA==null&&stringB==null){
            return true;
        }
        if(stringA==null||stringB==null){
            return false;
        }
        // write code here
        //每一个字符都有两个,异或结果为0
        char[] strs1=stringA.toCharArray();
        char[] strs2=stringB.toCharArray();
        int flag=(int)strs1[0]^(int)strs2[0];
        int i=1;
        for(;i<strs1.length;i++){
            flag^=(int)strs1[i]^(int)strs2[i];
        }
        if(i==strs2.length&&flag==0){
            return true;
        }
        return false;
    }
}

发表于 2019-09-05 10:55:14 回复(1)
# -*- coding:utf-8 -*-
class Same:
    def checkSam(self, stringA, stringB):
        return set(stringA)==set(stringB)
一行代码…利用原有的set判断字符出现的种类个数是否一致即可
发表于 2017-07-29 16:43:35 回复(2)
public boolean checkSam(String stringA, String stringB) {
        char [] ca = stringA.toCharArray();
		 char [] cb = stringB.toCharArray();
		 Arrays.sort(ca);
		 Arrays.sort(cb);
		 return Arrays.equals(ca,cb);
    }

发表于 2016-03-09 21:27:03 回复(2)
题目不够严谨:
1.题目中的测试用例诱导题目变为子字符串(单词)重排;
2.如果是字符重排,空格的影响要考虑不。

class Same {
public:
	bool checkSam1(string stringA, string stringB) {  //单词重排
		// write code here
		int lenA = stringA.size();
		int lenB = stringB.size();
		if (lenA ==0 || lenB ==0 || lenA != lenB)
			return false;
		vector<int> flagA = {0};
		for (int i = 0; i<lenA; i++){
			if (stringA[i] ==' '){
				flagA.push_back(i);
			}
		}
		flagA.push_back(stringA.size());
		vector<int> flagB = {0};
		string stringC = stringB;
		for (int i = 0; i<stringB.size()-1; i++){
			if (stringB[i] == ' '){
				flagB.push_back(i);
				stringB.erase(i, 1);
			}
		}
		flagB.push_back(stringB.size());
		if (flagA.size() != flagB.size())
			return false;
		string ch;
		for (int i = 0; i<flagB.size()-1; i++){
			ch.assign(stringB, flagB[i], flagB[i + 1] - flagB[i]);
			int findid = stringA.find(ch);
			if (findid == stringA.npos)
				return false;
		}
		return true;
	}
	bool checkSam2(string stringA, string stringB) {  //字符重排
		int lenA = stringA.size();
		int lenB = stringB.size();
		if (lenA == 0 || lenB == 0 || lenA != lenB)
			return false;
		int a[256] = { 0 };//用一张哈希表也可以
		int b[256] = { 0 };
		for (int i = 0; i < lenA; i++){  
			int idxA = stringA[i];
			int idxB = stringB[i];
				a[idxA] ++;
				b[idxB] ++;
		}
		for (int i = 0; i < 256; i++){
			if (a[i]!=b[i])
				return false;
		}
		return true;			
	}
};
测试:
        string sameA = "are you ok";
	string sameB = "you are ko";
	string sameC = "y ou are ko";
	Same sam;
	bool c1 = sam.checkSam1(sameA , sameB);//false
	bool c2 = sam.checkSam2(sameA , sameB);//true
	bool c3 = sam.checkSam2(sameC, sameB);//false

发表于 2017-08-18 22:40:21 回复(0)
class Same{
public:
bool checkSam(string stringA,string stringB){
int length=stringA.length();
if(length!=stringB.length())
return false;
else
{
int i=0,first=0;
char p;
for(;i<length;i++){
p=stringB[i];
for(first=i;first<length;first++){
if(stringB[first]==stringA[i]){
stringB[i]=stringB[first];
stringB[first]=p;
break;
}
else if(first+1==length)
return false;
}
}
if(i==length)
return true;
}
}
};
发表于 2017-03-02 18:41:02 回复(0)
思路:A字符串中字符编排能够等到B字符串则为true,否则为false。也就是说A字符串有的字符在B字符串中也必须有,且数量相同。由此直接对A,B字符串排序后进行比较,相同为true,不同为false。
public class Same {
    public boolean checkSam(String stringA, String stringB) {
        if (stringA.length() != stringB.length()) {
            return false;
        }
        char[] arrayA = stringA.toCharArray();
        char[] arrayB = stringB.toCharArray();
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        System.out.println(new String(arrayA) + ":" + new String(arrayB));
        if (!new String(arrayA).equals(new String(arrayB))) {
            return false;
        }
        return true;
    }
}
编辑于 2015-08-29 16:58:07 回复(2)
bool checkSam(string stringA, string stringB) {
        // write code here
        int lenA = stringA.length();
        int lenB = stringB.length();
        if(lenA == lenB){
            int t = 0;
            for(int i=0; i<lenA; i++){
                t ^= stringA[i];
                t ^= stringB[i];
            }
            if(t == 0){
                return true;
            }
        }
        return false;
    }
发表于 2015-07-22 09:57:30 回复(4)
  • 思路:用hashMap来实现
import java.util.*;
    public class Same {
    public boolean checkSam(String stringA, String stringB) {
        if(stringA==null || stringB==null){
            return false;
        }
        if(stringA.length() != stringB.length() ){
            return false;
        }
        //Map用于存放键值和键值出现的次数
        HashMap mapA=new HashMap();
        HashMap mapB=new HashMap();
        int lenA=stringA.length();
        int lenB=stringB.length();
        int i;
        Integer temp=new Integer(0);
        //计算A串中每个键值的出现的次数,首次压入字符,value值为1;非首次压入的字符,value=value+1
        for(i=0;i<lenA;i++){
            temp=mapA.get(stringA.charAt(i));
            if(temp!=null){
                mapA.put(stringA.charAt(i),temp+1);
            }else{
                mapA.put(stringA.charAt(i),1);
            }
        }
        //同串A的操作
        for(i=0;i<lenB;i++){
            temp=mapB.get(stringB.charAt(i));
            if(temp!=null){
                mapB.put(stringB.charAt(i),temp+1);
            }else{
                mapB.put(stringB.charAt(i),1);
            }
        }
        //遍历mapA,若mapA中的键mapB未出现,或者mapA中的键的值与mapB中的不同,则返回false
        for(Map.Entry entry:mapA.entrySet()){
            if((temp=mapB.get(entry.getKey()))!=null){
                if(temp.equals(entry.getValue()))
                    continue;
                else
                    return false;
            }else{
                return false;
            }
        }
        //若遍历过程未返回false,则说明两个map内容完全一样,返回true
        return true;
    }
    }
发表于 2018-04-07 20:42:48 回复(0)
苦思冥想想不出怎么做,看了讨论区知道可以通过字符出现的次数做判断
于是想到曾用过一个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)
class Same {
public:
    bool checkSam(string stringA, string stringB) {
        if(stringA.size()!=stringB.size())
            return false;
        bool state[stringB.size()];
        bool flag;
        fill(state,state+stringB.size(),0);
        for(int i=0;i<stringA.size();++i)
        {
            flag=false;
            for(int j=0;j<stringB.size();++j)
            {
                if(state[j]==1) continue;
                if(stringA[i]==stringB[j]) {flag=true;state[j]=1;break;}
            }
            if(!flag) return false;
        }
        return true;
    }
};
//可以用哈希表

编辑于 2019-05-01 19:32:01 回复(0)
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)
class Same {
public:
    bool checkSam(string A, string B) {
        if(A.length() != B.length()||A.empty())
            return false;
        sort(A.begin(),A.end());
        sort(B.begin(),B.end());
        return (A ==B);
    }
};
发表于 2018-01-18 16:37:06 回复(0)
bool checkSam(string stringA, string stringB) {
        int ch[128];
        for(int i = 0; i < 128; i++)
            ch[i] = 0;
        for(size_t i = 0; i < stringA.size(); i++)
            ch[stringA[i] - 'A']++;
        for(size_t i = 0; i < stringB.size(); i++)
            ch[stringB[i] - 'A']--;
        for(int i = 0; i < 128; i++)
            if(ch[i] != 0) return false;
        return true;
    }
O(1)空间,O(n)时间,以字母在ASCII表中出现的序号为数组ch的下标。当且仅当ch每一个元素都为0时返回true,否则返回false。
发表于 2017-09-27 10:31:55 回复(1)