leetcode-字符串-242-有效的字母异位词

leetcode

算法

发布日期: 2020-05-16

作者: 朝飞

文章字数: 678

阅读时长: 2 分

阅读次数:

242.有效的字母异位词

描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1

    输入: s = "anagram", t = "nagaram"
    输出: true

示例 2

    输入: s = "rat", t = "car"
    输出: false

思路 1

1.将字符串转成数组
2.利用数组sort方法进行排序
3.将数组转成字符串，依次比较字符是否相等，如果全相等，返回true，否则返回false

解法 1

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    // 先判断两个字符串长度是否相等，不相等直接返回false
    if (s.length !== t.length) {
        return false;
    }

   // 将字符串转成数组
   let sArr = s.split('');
   let tArr = t.split('');

   // 排序函数
   const sortFn = (a,b) => a.charCodeAt() - b.charCodeAt();

   // 进行排序
   sArr.sort(sortFn);
   tArr.sort(sortFn);

   // 依次比较字符
   return sArr.join('') === tArr.join('');
};

复杂度分析 1

时间复杂度：O(nlogn)
- JavaScript 的 sort 方法的实现原理，当数组长度小于等于 10 的时候，采用插入排序，大于 10 的时候，采用快排，快排的平均时间复杂度是。
空间复杂度：O(n)
- 算法中申请了 2 个数组变量用于存放字符串分割后的字符串数组，所以数组空间长度跟字符串长度线性相关，所以为。

思路 2

1.定义一个对象，遍历其中的一个字符串，对每个字符串的个数累加
2.遍历另一个字符串，使每一个字母在已得到的对象中做匹配，如果匹配则对象下的字母个数减 1，如果匹配不到，则返回 false，如果最后对象中每个字母个数都为 0，则表示两字符串相等。

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    // 先判断两个字符串长度是否相等，不相等直接返回false
    if (s.length !== t.length) {
        return false;
    }
    // 定义一个对象，
    const hash = {};

    // 遍历字符串s，看每个字符的个数，最后形成
    // hash = { a: 3, n: 1, g: 1, r: 1, m: 1 }
    for (const k of s) {
        hash[k] = hash[k] || 0;
        hash[k] += 1;
    }

    // 然后遍历字符串t
    for (const k of t) {
        // 判断字符串t中的每个字符是否在hash中，不在，则返回false
        if (!hash[k]) {
            return false;
        }
        // 说明匹配成功，把遍历的字符个数减一
        hash[k] -= 1;
    }
    return true;
};