242. 有效的字母异位词

思路

字母异位词:使用字母相同和相同字母的个数也相同,构成不同的单词。

利用哈希表+生产消费的概念。

  1. 遍历第一个单词,将所有的字符存储哈希表中,并记录次数(视为生产者);
  2. 遍历第二个单词,若当前字符在哈希表中存在,此字符在哈希表中的次数减一(视为消费者); 若不存在,则两个单词不是异位词;
  3. 遍历哈希表,判断每个元素的值是否为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;
    }
}

results matching ""

    No results matching ""