易位词的匹配

易位词的匹配

2019独角兽企业重金招聘Python工程师标准>>>

来源于一道微软面试题，如下

两个单词如果包含相同的字母，次序不同，则称为字母易位词(anagram)．例如, silent和listen是字母易位词，而apple和aplee不是易位词．请定义函数，检查两个单词是否是字母易位词．可以假设两个单词字母均为小写．要求算法复杂度尽量低．

观察易位词，发现三个特点

1, 长度相同;

2, 前面单词出现过的字母，也一定在后面的单词中出现过;

3, 同一个字母在前面和后面的单词中出现的次数相同;

思路一

对前面单词的每个字母进行循环遍历，看是否在后面出现过，如果出现过，则将出现的那个字母删除，然后进行下一次循环．这里用PHP来实现.

//将一个单词转化为数组
function wordToArray($str=''){$str = is_string($str) ? trim($str) : trim($str.'');$len = strlen($str);$arr = array();if($len>0){for($i=0;$i<$len;$i++){$arr[]=$str[$i];}}return $arr;
}//检查两个字符串是否互为字母易位词
function checkAnagram($a='',$b=''){//强制转换为字符串$a = is_string($a) ? trim($a) : trim($a.'');$b = is_string($b) ? trim($b) : trim($b.'');//转化为数组$a = wordToArray($a);$b = wordToArray($b);//检查字符串长度$len1 = count($a);$len2 = count($b);if($len1 != $len2){return false;}//对第一个字符串进行循环遍历for($i=0;$i<$len1;$i++){//相同次数初始化$sameTime = 0;//对第二个字符串进行遍历for($j=0;$j<$len2;$j++){//如果第一个字符串中某个字母在第二个字符串中被第一次找到if($a[$i] === $b[$j]){//如果找到相同的字母+1$sameTime++;//则将第二个字符串中的该字母删除，也就是用空字符串将其替代unset($b[$j]);//删除后不继续往下遍历，开始第一个字符串中下一个字母的循环遍历break;}}//如果遍历玩第二个单词一次相同的字母都没有找到则为否if(empty($sameTime)) return false;}//如果第二个字符串的所有字母都被删除了，说明第一个字符串中的字母都在第二个字符串中且出现次数相等return empty($b) ? true : false;
}

用 silent和listen做测试

$a = checkAnagram('silent','listen');
var_dump($a);

结果为真

/opt/wwwroot/test/test7.php:157:boolean true

用 apple和aplle做测试，结果为否

/opt/wwwroot/test/test7.php:157:boolean false

测试OK

思路二

易位词组成的字母是相同的，只是顺序不同，如果按照字母顺序排序后，两者应该完全一样．

//将一个单词转化为数组
function wordToArray($str=''){$str = is_string($str) ? trim($str) : trim($str.'');$len = strlen($str);$arr = array();if($len>0){for($i=0;$i<$len;$i++){$arr[]=$str[$i];}}return $arr;
}function checkAnagram($a='',$b=''){//强制转换为字符串$a = is_string($a) ? trim($a) : trim($a.'');$b = is_string($b) ? trim($b) : trim($b.'');//转化为数组$a = wordToArray($a);$b = wordToArray($b);//检查字符串长度$len1 = count($a);$len2 = count($b);if($len1 != $len2){return false;}//对两个单词的字母按字母顺序排序，返回排序后的新数组sort($a);sort($b);//如果两个数组相同，返回真return ($a==$b)? true : false;
}

用 silent 和 listen 测试，返回真

$a = checkAnagram('silent','listen');
var_dump($a);

/opt/wwwroot/test/test7.php:183:boolean true

用 apple 和 aplle 测试，返回否

$a = checkAnagram('apple','aplle');
var_dump($a);

/opt/wwwroot/test/test7.php:184:boolean false

比方法一更轻松些

思路三

易位词的字母组成是一样的并且字母出现的次数一致，那么可以对每个字母做计数，然后对比两组计数，相同则为真

function checkAnagram($str1='',$str2=''){//强制转换为字符串$str1 = is_string($str1) ? trim($str1) : trim($str1.'');$str2 = is_string($str2) ? trim($str2) : trim($str2.'');//检查字符串长度$len1 = strlen($str1);$len2 = strlen($str2);if($len1 != $len2){return false;}//字符串计数器初始化$arr1 = $arr2 = array();//对第一个字符串做遍历计数for($i=0;$i<$len1;$i++){//获取字母在字母表中的位置$pos = ord($str1[$i]) - ord('a');//每出现一次就在该位置上计数+1$arr1[$pos] +=1;}//对第二个字符串做遍历计数for($j=0;$j<$len1;$j++){//获取字母在字母表中的位置$pos = ord($str2[$j]) - ord('a');//每出现一次就在该位置上计数+1$arr2[$pos] +=1;}//对两个数组做比较return ($arr1==$arr2)? true : false;
}

用 silent 和 listen 测试，返回真

$a = checkAnagram('silent','listen');
var_dump($a);

/opt/wwwroot/test/test7.php:183:boolean true

用 apple 和 aplle 测试，返回否

$a = checkAnagram('apple','aplle');
var_dump($a);

/opt/wwwroot/test/test7.php:184:boolean false

比较三种思路的计算量

第一种思路是遍历里面再次遍历，一共有n(n+1)/2次运算，复杂度为O(n^2)；

第二种思路看起来只是对每个字母做了一次比较，也就是n个计算量．但实际上在比较之前，分别对两个字符串做了排序处理，把排序运算包括进去后就是（n*logn+n）次运算，复杂度为O(n*logn)；

第三种思路分别对字符串进行了遍历，最后进行了一次比较，所以计算量为min(n+n+n, n+n+26)，复杂度为O(n);

算法复杂度

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。

求两个n阶方阵的乘积 C=A×B,其算法如下:

# define n 100 // n 可根据需要定义,这里假定为100
void MatrixMultiply(int A[n][n]，int B [n][n]，int C[n][n])
{ //右边列为各语句的频度int i ,j ,k;for(i=0; i<n;i++) //n+1for (j=0;j<n;j++) { //n(n+1)C[i][j]=0; //n²for (k=0; k<n; k++) //n²(n+1)C[i][j]=C[i][j]+A[i][k]*B[k][j];//n³}
}

T(n)=2n3+3n2+2n+1 (1.1)该算法中所有语句的频度之和(即算法的时间耗费)为：

分析：

语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。

算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。

思考

忽然想起了廖老师．

转载于: