242. 有效的字母异位词
思路
字母异位词:使用字母相同和相同字母的个数也相同,构成不同的单词。
利用哈希表+生产消费的概念。
- 遍历第一个单词,将所有的字符存储哈希表中,并记录次数(视为生产者);
- 遍历第二个单词,若当前字符在哈希表中存在,此字符在哈希表中的次数减一(视为消费者); 若不存在,则两个单词不是异位词;
- 遍历哈希表,判断每个元素的值是否为0,若为0,则证明全部消费掉,即两个单词是异位词; 若存在有不为0的,则没全部消费掉,即两个单词不是异位词。
复杂度
时间复杂度:O(n)
空间复杂度:O(m)
代码
class Solution {
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isAnagram($s, $t) {
$hash = [];
// 生产
for($i = 0; $i < strlen($s); $i++) {
if(isset($hash[$s[$i]])) {
$hash[$s[$i]] += 1;
} else {
$hash[$s[$i]] = 1;
}
}
// 消费
for($i = 0; $i < strlen($t); $i++) {
if(isset($hash[$t[$i]])) {
$hash[$t[$i]] -= 1;
} else {
return false;
}
}
// 判断hash中的每个字母是否全部消费掉
foreach($hash as $value) {
if($value != 0 ) {
return false;
}
}
return true;
}
}