242. Valid Anagram

Leetcode 问题: 242. Valid Anagram
Categories:
Tags:

题目

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

传入 2 个字串 s 及 t，比较这 2 个字串，彼此字母出现的次数是否都相同，如果相同则为 Anagram 字串，回传 true，如果有不同的字，则回传 false

Example

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

演算法 1. 产生字母对应 Map

1. 产生字串字母对应次数 Map

将两个字串字母出现次数记录到 Map

2. 比较字母出现次数是否相同

当遇到有字母出现次数不同的状况，则这两个字串 不是 Anagram 字串，所以回传 false

如果字母出现次数都相同，则 是 Anagram 字串，回传 true

演算法 1. 答案

JavaScript

function isAnagram(originalText, compareText) {
    if (originalText.length != compareText.length) {
        // 字串长度不同，不用比较，一定不是 anagram
        return false;
    }
    var originalLetterMap = new Map();
    var compareLetterMap = new Map();
    for (var i = 0; i < originalText.length; i++) {
        // 原始字母
        var originalLetter = originalText[i];
        // 比较字母
        var compareLetter = compareText[i];
        // 原始字母出现次数
        var originalLetterCount = originalLetterMap.get(originalLetter);
        // 比较字母出现次数
        var compareLetterCount = compareLetterMap.get(compareLetter);
        if (!originalLetterCount) {
            // 没有原始字母，第一次出现预设为 0
            originalLetterCount = 0;
        }
        if (!compareLetterCount) {
            // 没有比较字母，第一次出现预设为 0
            compareLetterCount = 0;
        }
        // 设定字母出现次数
        originalLetterCount++;
        compareLetterCount++;
        originalLetterMap.set(originalLetter, originalLetterCount);
        compareLetterMap.set(compareLetter, compareLetterCount);
    }
    // 预设是 Anagram 文字
    var isAnagramText = true;
    for (var _i = 0, _a = originalLetterMap.entries(); _i < _a.length; _i++) {
        var _b = _a[_i], originalLetter = _b[0], originalLetterCount = _b[1];
        // 比较的字幕出现次数
        var compareLetterCount = compareLetterMap.get(originalLetter);
        if (originalLetterCount != compareLetterCount) {
            // 如果出现的次数不相同，不是 Anagram
            isAnagramText = false;
            break;
        }
    }
    return isAnagramText;
}

TypeScript

function isAnagram(originalText: string, compareText: string): boolean {
    if (originalText.length != compareText.length) {
        // 字串长度不同，不用比较，一定不是 anagram
        return false;
    }

    let originalLetterMap = new Map();
    let compareLetterMap = new Map();

    for (let i = 0; i < originalText.length; i++) {
        // 原始字母
        let originalLetter = originalText[i];
        // 比较字母
        let compareLetter = compareText[i];
        // 原始字母出现次数
        let originalLetterCount = originalLetterMap.get(originalLetter);
        // 比较字母出现次数
        let compareLetterCount = compareLetterMap.get(compareLetter);

        if (!originalLetterCount) {
            // 没有原始字母，第一次出现预设为 0
            originalLetterCount = 0;
        }
        if (!compareLetterCount) {
            // 没有比较字母，第一次出现预设为 0
            compareLetterCount = 0;
        }

        // 设定字母出现次数
        originalLetterCount++;
        compareLetterCount++;
        originalLetterMap.set(originalLetter, originalLetterCount);
        compareLetterMap.set(compareLetter, compareLetterCount);
    }

    // 预设是 Anagram 文字
    let isAnagramText = true;
    for (const [originalLetter, originalLetterCount] of originalLetterMap.entries()) {
        // 比较的字幕出现次数
        let compareLetterCount = compareLetterMap.get(originalLetter);

        if (originalLetterCount != compareLetterCount) {
            // 如果出现的次数不相同，不是 Anagram
            isAnagramText = false;
            break;
        }
    }

    return isAnagramText;
};

演算法 2. 对字母排序

如果瞭个字串是 Anagram 字串 的话，那麽排序后的字母也应该是相同的

所以将字母排序后，在比较彼此是否相同，若相同则 是 Anagram 字串，回传 true

若不同则 不是 Anagram 字串，回传 false

参考资料