泰安北京网站建设公司哪家好,普宁建设局网站,网站建设 杭州,怎样登录建设互联网站1. 题目描述
给定两个仅包含小写字母的字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的 字母异位词。
字母异位词定义#xff1a;两个字符串包含的字母种类和数量完全相同#xff0c;但顺序可以不同#xff08;例如 “listen” 和 “silent”#xff09;。 …1. 题目描述
给定两个仅包含小写字母的字符串 s 和 t 编写一个函数来判断 t 是否是 s 的 字母异位词。
字母异位词定义两个字符串包含的字母种类和数量完全相同但顺序可以不同例如 “listen” 和 “silent”。
原题链接[242]
2. 解题思路
使用哈希表的方式实现。 哈希表底层可以用一个数组实现将两个字符串的字符映射到哈希表的每个索引中然后依次对比两个哈希表内的元素是否一致即可。
关键在于如何构建哈希函数。
根据题目两个字符串都只包含小写字母最多26个小写字母所以构建哈希表的大小为26即可字母a放到索引0字母z放到索引25依次填入。 而如何将字母放到对应的索引中 根据代码原理字符本质上是基于 ASCII 码值的整数a到z对应是连续的ASCII 码值所以 ‘a’ - ‘a’是0‘b’ - ‘a’是1以此类推可以得到a的索引是0b的索引是1c的索引是2…这样就可以将字符串内的字符按规则填入哈希表的对应索引中进行比较。
3. C语言实现
3.1 双哈希表
bool isAnagram(char* s, char* t) {int lens strlen(s), lent strlen(t);if(lens ! lent)return false;int map1[26] {0} , map2[26] {0};for(int i 0; i lens; i){map1[s[i] - a] 1;map2[t[i] - a] 1;}for(int i 0; i 26; i){if(map1[i] ! map2[i]){return false;}}return true;
}首先判断两个数组的长度是否相等长度不相等肯定不是字母异位词。定义两个哈希表map1和map2长度设置为26初始化全为0。for循环遍历两个字符串s和ts[i] - a’即表示字符串s中第i个位置的字符该对应于哈希表map1的第几个索引位置得到索引之后在map1的相应索引处加1代表该处有一个元素。map2同理。for循环遍历map1和map2的26个索引检查两个哈希表是否一致不一致则返回false表示两个字符串不是有效的字母异位词。
3.2 单哈希表
上面是用两个哈希表对应两个字符串遍历到字符时在对应的哈希表内加1计数可以优化一下使用全为0的单哈希表遍历s时在哈希表对应索引增加计数遍历t时在哈希表对应索引减少技术最后检查哈希表是不是全为0如果有的索引还有计数则说明两个字符串含有数量不一样的字符不是有效的字母异位词很好理解。
bool isAnagram(char* s, char* t){int lens strlen(s);int lent strlen(t);if(lent ! lens)return false;int map[26] {0};for(int i 0; i lens; i){map[s[i] - a] 1;}for(int i 0; i lens; i){map[t[i] - a] - 1;}for(int i 0; i 26; i){if(map[i] ! 0)return false;}return true;
}
