20200606-242.valid-anagram.md

#242.valid-anagram

题目链接：https://leetcode-cn.com/problems/valid-anagram/

参考链接：https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode/

题目

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

示例1 :

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

示例 2:

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

说明: 你可以假设字符串只包含小写字母。

解题

思路[1]hashMap

• 使用hashMap记录每个字符出现的次数，遍历两边即可，一遍记录，一遍查询
• 然后比较两个字符串是不是相同，如果不同则返回false。
• 第一种是两个映射分别记录
• 第二种是记录一个映射，第一个字符串+，第二个字符串--，然后如果都是0则说明是异位词

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  if(s.length !== t.length){
    return false
  }
  var obj1 = {}, obj2 = {};
  for(var i = 0; i < s.length; i++){
    obj1[s[i]] = (obj1[s[i]] || 0) + 1;
    obj2[t[i]] = (obj2[t[i]] || 0) + 1;
  }
  for(var i = 0; i < s.length; i++){
    let item = s[i];
    if(obj1[item] !== obj2[item]){
      return false
    }
  }
  return true
};

var isAnagram = function(s, t) {
  if(s.length !== t.length){
    return false
  }
  var obj = {};
  for(var i = 0; i < s.length; i++){
    obj[s[i]] = (obj[s[i]] || 0) + 1;
    obj[t[i]] = (obj[t[i]] || 0) - 1;
  }
  for(var i = 0; i < s.length; i++){
    let item = s[i];
    if(obj[item] !== 0){
      return false
    }
  }
  return true
};

思路[2]排序

• 先排序然后比较字符串

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  var s_str = s.split('').sort().join('')
  var t_str = t.split('').sort().join('')
  return s_str === t_str
};

思路[3]桶查询

• 一共26个位置，判断26个字母出现的个数，然后判断是否全是0

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s === t) { return true; }
    if (s.length !== t.length) { return false; }
    const map = new Array(26).fill(0);
    for(let i = 0; i < s.length; i++) {
        map[s.charCodeAt(i) - 97]++;
        map[t.charCodeAt(i) - 97]--;
    }
    return map.every((a) => a === 0 );
};

思考

• 第一思路就是hashMap，但题目中告诉你是小写字母所以这一定是有用的，忽略了这个点
• 排序这种思路还是忽略了，最后如果要判断字母包含相同，字符串构成相同，数组构成相同则可以使用排序