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

參考資料