You can add wechat: sxxzs3998 (note CSDN) if you want to join the interview question brushing group of large factories

1. Title

If the characters of two strings are the same but the order is different, they are considered brother strings. Ask how to quickly match brother strings (for example, bad and adb are brother strings)

2. Analysis

2.1 polling method of O (n*m)

Judge whether the characters in string2 are in string1: String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPO

The most intuitive and simple way to judge whether a string is in another string is to poll and compare each character in the second string string2 with each character in the first string string1 to see whether it is in the first string string1.

2.2 sorting method of O (mlogm) + O (nlogn) + O (M + n)

A slightly better solution is to sort the letters of the two strings first, and then poll the two strings at the same time. The sorting of two strings requires (generally) O(mlogm) + O(nlogn) operations, and the subsequent linear scan requires O(m+n) operations.

The steps are as follows: 1. Judge whether the length of the two strings is the same. If not, exit. 2. Each string is sorted by character. For example, abc is followed by acb. If it is a brother string, it is the same after sorting.

2.3 Hashmap

Create two hash arrays, record two strings respectively, and then compare whether each item of the two arrays is the same. There are different descriptions, not brother strings

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;  
 
int main()
{
	int hash1[256],hash2[256],i,len1,len2;
	char str1[100],str2[100]; 
	
	printf("Please enter 2 strings: (0 ends)\n");
	while(1)
	{
		//input 
		scanf("%s",str1);
		if(!strcmp(str1,"0")) break;
		scanf("%s",str2);
		
		//Comparison length 
		len1=strlen(str1);
		len2=strlen(str2);
		if(len1!=len2)
		{
			printf("%s,%s,They are not sibling strings\n",str1,str2);
			continue;
		}
		 
		//Are the characters the same 
		memset(hash1,0,sizeof(hash1));
		memset(hash2,0,sizeof(hash2));
		for(i=0;i<len1;i++)
		{
			hash1[str1[i]]++;
			hash2[str2[i]]++;
		} 
		for(i=0;i<255;i++)
		{
			if(hash1[i]!=hash2[i])//Different 
				break;
		}
		if(i==255)
			printf("%s,%s,Both are sibling strings\n",str1,str2);
		else
			printf("%s,%s,They are not sibling strings\n",str1,str2);
	}
}
/*
bad abd
abcd abc
aabbccdd abcdabcd
abcdabc aabbccc
aaa bbb
ababa babab
ababa aabba
0
*/

2.4 prime number method from O (n) to o (n+m)

You may think that O(n+m) is the best result you can get. You need to visit each letter at least once to complete this operation, while the last two schemes in the previous section happen to visit each letter only once.

Assign prime numbers to 26 characters in turn. Prime numbers are a special bunch of numbers, which can only be divided by 1 and itself. Assign 2 to a, 3 to b, 5 to c, 7 to d, 11 to e and 13 to f.

Addition: all characters in the two strings are assigned values, and then they are added respectively. If the results of the two strings are the same, they are brother strings. However, b+f=3+13=16; c+e=5+11=16, so there is an error;

Multiplication: all characters in two strings are multiplied by each other. The method is correct, but it will overflow, so it needs to be handled as a large integer; Use square sum or cubic sum: consider whether the square sum will solve the error of addition, and the multiplication overflow: bb+ff=33+1313=178; cc+ee=55+1111=146

Then -- poll the second string and divide it by each letter. If the result of division has a remainder, it indicates that there are mismatched letters. If there is no remainder in the whole process, you should know that it is the exact subset of the first string.

If it is an addition, a data structure similar to set can be used to record the frequency of letters in the string, but the space overhead will be greater than that of prime numbers (the prime number method requires space to allocate prime numbers, although it is a constant level). The code is as follows:

/*
If the characters of two strings are the same, but the order is different, they are considered brother strings,
Ask how to quickly match sibling strings (for example, bad and adb are sibling strings).
*/
#include <iostream>
using namespace std;
 
int isBroStr(char *str1, char *str2)
{
    int a[26 * 2] = {0};
    int i, strLen;
    
    if (!str1 && !str2)
        return 1;
    else if (!str1 || !str2)
        return 0;
    else
    {
        if(strlen(str1) != strlen(str2))
            return 0;
        strLen = strlen(str1);
        for(i = 0; i < strLen; i++)
        {
            ++a[str1[i] - 'A'];
            --a[str2[i] - 'A'];
        }
        for(i = 0; i < 26 * 2; i++)
            if (a[i])
                return 0;
        return 1;
    }        
}
 
int main()
{
    char *str1 = "asdfaabAAB";
    char *str2 = "asdfAABaab";
    if (isBroStr(str1, str2))
        cout << " String 1 and String 2 are brothers!" << endl;
    else
        cout << " String 1 and String 2 are not brothers!" << endl;
    system("PAUSE");
    return 0;
}

You can add wechat: sxxzs3998 (note CSDN) if you want to join the interview question brushing group of large factories