A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

1. The subject

If two strings have the same characters, but in different order, they are considered sibling strings, ask how to quickly match sibling strings (for example, bad and ADB are sibling strings)

2.

2.1 O (n*m) polling method

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

The most intuitive and simplest way to determine whether a string is in another string is to poll each character in the second string, string2, against each character in the first string, string1, to see if it is in the first string, string1.

2.2 Sorting method of O(mlogm)+O(nlogn)+O(m+n)

A slightly better solution would be to sort the two strings alphabetically first and then poll for both strings in turn. Ordering two strings requires (in the general case)O(mlog M) + O(nlogn) operations, and subsequent linear scans require O(m+ N) operations.

The procedure is as follows: 1. Check whether the lengths of the two strings are the same. If they are different, exit. 2, each string is sorted by character, such as acB sort followed by ABC, if the brother string, after the sorting is the same.

2.3 a Hashmap

Create two hash arrays, record two strings separately, and then compare each item of the two arrays to see if it is the same and has a different description that is not a sibling string

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;  
 
int main(a)
{
	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);
		
		// Compare lengths
		len1=strlen(str1);
		len2=strlen(str2);
		if(len1! =len2) {printf("%s,%s, they are not brothers string \n",str1,str2);
			continue;
		}
		 
		// Whether the characters are 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, the two are brothers string \n",str1,str2);
		else
			printf("%s,%s, they are not brothers string \n",str1,str2); }}/*
bad abd
abcd abc
aabbccdd abcdabcd
abcdabc aabbccc
aaa bbb
ababa babab
ababa aabba
0
*/

Copy the code

2.4 Prime number method from O (n) to O (n+m)

You might think that O(n+m) is the best you can get, and that you need to do this at least once per letter, whereas the last two schemes in the last section did exactly once per letter.

Assign prime numbers to each of the 26 characters in turn. Prime numbers are a special bunch of numbers that are divisible only by 1 and themselves. Assign 2 to A, 3 to B, 5 to C, 7 to D, 11 to E and 13 to F.

Addition: All characters in two strings are assigned, and then they are added to each other. If both strings give the same result, they are sibling strings. However, b+f=3+13=16; C +e=5+11=16

Multiplication: Multiply all the characters in two strings individually. This is the right method, but it will overflow, so you have to deal with large integers. Using sums of squares or cubes: Consider if sums of squares will solve the addition error, multiplication overflow: bb+ff=33+1313=178; cc+ee=55+1111=146

Then — polling the second string, dividing it by each letter. If the result of division has a remainder, it means there are mismatched letters. If there’s no remainder, you should know that it’s an exact subset of the first string.

In addition, a data structure similar to a set is used to record the frequency of letters in the string, but the space overhead is greater than for prime numbers (the prime method also requires space for allocating prime numbers, albeit at a constant level). The code is as follows:

/* If two strings have the same characters, but in different order, they are considered sibling 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(a)
{
    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;
}
Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast