确定两串乱序同构

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):如果两个数组以相同顺序包含相同的元素，则两个数组是相等的
    }
}

//先判断大小是否相同。不同则直接返回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;
    }
};

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;
    }
};

//有点无耻额，直接用的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;
    }
};

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();
    }
}

# -*- coding:utf-8 -*-
class Same:
    def checkSam(self, stringA, stringB):
        return set(stringA)==set(stringB)

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);
    }

题目不够严谨：
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

• 思路：用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;
    }
    }

class Same {
public:
    bool checkSam(string stringA, string stringB) {
        // write code here
        sort(stringA.begin(),stringA.end());
        sort(stringB.begin(),stringB.end());
        return stringA == stringB;
    }
};

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;
    }
}

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;
    }
};
//可以用哈希表

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);
    }
};

if(stringA.length()!=stringB.length())
			return false;
		char[] ch1=stringA.toCharArray();
		char[] ch2=stringB.toCharArray();
		 Arrays.sort(ch1);
		 Arrays.sort(ch2);
		return   (Arrays.toString(ch1)).equals(Arrays.toString(ch2));

 # -*- coding:utf-8 -*-
class Same:
    def checkSam(self, stringA, stringB):
        # write code here
        recordA=[0]*256
        recordB=[0]*256
        for ch in stringA:
            ch_val=ord(ch)
            recordA[ch_val]=recordA[ch_val]+1
            
        for ch in stringB:
            ch_val=ord(ch)
            recordB[ch_val]=recordB[ch_val]+1
        
        for i in range(256):
            if recordA[i]!=recordB[i]:
                return False
            
        return True
if __name__=='__main__':
    strA=raw_input()
    strB=raw_input()
    sm=Same()
    print(sm.checkSam(strA,strB))