【微软算法面试高频题】兄弟字符串 1题目 2解析

发表于

微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注掘金），进群参与讨论和直播

1.题目

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）

2.解析

2.1 O（n*m）的轮询方法

判断string2中的字符是否在string1中： String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPO

判断一个字符串是否在另一个字符串中，最直观也是最简单的思路是，针对第二个字符串string2中每一个字符，与第一个字符串string1中每个字符依次轮询比较，看它是否在第一个字符串string1中。

2.2 O(mlogm)+O(nlogn)+O(m+n)的排序方法

一个稍微好一点的方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(mlogm) + O(nlogn)次操作，之后的线性扫描需要O(m+n)次操作。

步骤如下： 1、判断两个字符串的长度是否一样,如果不一样则退出。 2、每个字符串按字符排序，如acb排序之后是abc,如果是兄弟字符串的话，排序之后是一样的。

2.3 Hashmap

建两个hash数组，分别记录两个字符串，然后比较两个数组的每一项是否相同，有不同的说明不是兄弟字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
c++复制代码#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("请输入2个字符串：（0结束）\n");
	while(1)
	{
		//输入 
		scanf("%s",str1);
		if(!strcmp(str1,"0")) break;
		scanf("%s",str2);
		
		//比较长度 
		len1=strlen(str1);
		len2=strlen(str2);
		if(len1!=len2)
		{
			printf("%s,%s,二者不是兄弟字符串\n",str1,str2);
			continue;
		}
		 
		//字符是否相同 
		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])//不同 
				break;
		}
		if(i==255)
			printf("%s,%s,二者是兄弟字符串\n",str1,str2);
		else
			printf("%s,%s,二者不是兄弟字符串\n",str1,str2);
	}
}
/*
bad abd
abcd abc
aabbccdd abcdabcd
abcdabc aabbccc
aaa bbb
ababa babab
ababa aabba
0
*/

2.4 O（n）到 O（n+m）的素数方法

你可能会这么想：O(n+m)是你能得到的最好的结果了，至少要对每个字母至少访问一次才能完成这项操作，而上一节最后的俩个方案是刚好是对每个字母只访问一次。

给26个字符依次赋予质数。质数是比较特殊的一堆数字，它们只能被1和本身整除。以给a赋值2、给b赋值3、给c赋值5、给d赋值7、给e赋值11、给f赋值13。

加法：两个字符串中的所有字符都赋值了，接着让它们各自相加，如果两个字符串得出的结果是一样的，那它们是兄弟字符串。但是，b+f=3+13=16；c+e=5+11=16，所以有误；

乘法：两个字符串中的所有字符让它们各自相乘，方法是对的，但是会溢出，所以要大整数处理了；用平方和或者立方和：考虑平方和会不会解决加法有误，乘法溢出：bb+ff=33+1313=178；cc+ee=55+1111=146

然后——轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。

如果是加法，那么使用一个类似于set的数据结构来记录字符串中字母出现的频次即可,但是空间开销会比素数更大（素数法要求分配素数也是需要空间的，虽然是常数级）。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
c++复制代码/*
如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，
问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。
*/
#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;
}

微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注掘金），进群参与讨论和直播

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%