205. Isomorphic Strings

Leetcode 問題: 205. Isomorphic Strings
Categories:
Tags:

題目

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

傳入 2 個字串 s 和 t 判斷這兩個字串是不是互相是 Isomorphic 字串

Isomorphic 字串表示彼此的字母可以透過 Map 互相轉換，而不會掉字及順序，也要能彼此互相轉換

Example

Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

Input: s = "paper", t = "title"
Output: true

演算法

1. 產生原始及比較字母對應 Map

因為 原始字串 及 比較字串 彼此的每個字母及位置都要能夠互相對應轉換

所以 原始字串的字母 要能夠對應到 比較字串的字母，且 比較字串的字母 也要能夠對應到 原始字串的字母

如果不能彼此互相轉換，則不是 Isomorphic 字串

2. 比較字串每個字母

  • 如果「原始文字字母對應」已有「對應的字母」，且「對應的字母」與「比較的字母」不一樣
  • 如果「比較文字字母對應」已有「對應的字母」，且「對應的字母」與「原始的字母」不一樣

表示這個不是 Isomorphic 字串

答案

JavaScript

function isIsomorphic(originalText, compareText) {
    if (originalText.length == 0 || originalText.length != compareText.length) {
        // 如果傳入字串長度不同或空字串
        return false;
    }
    // 字母對應 Map
    var originalTextMap = new Map();
    var compareTextMap = new Map();
    for (var i = 0; i < originalText.length; i++) {
        // 取得比較的字母
        var originalLetter = originalText[i];
        var compareLetter = compareText[i];
        if ((originalTextMap.has(originalLetter) && originalTextMap.get(originalLetter) != compareLetter)
            || compareTextMap.has(compareLetter) && compareTextMap.get(compareLetter) != originalLetter) {
            // 如果「原始文字字母對應」已有「對應的字母」，且「對應的字母」與「比較的字母」不一樣
            // 如果「比較文字字母對應」已有「對應的字母」，且「對應的字母」與「原始的字母」不一樣
            // 表示這個不是 Isomorphic 字串
            return false;
        }
        // 設定字母對應表
        originalTextMap.set(originalLetter, compareLetter);
        compareTextMap.set(compareLetter, originalLetter);
    }
    return true;
}

TypeScript

function isIsomorphic(originalText: string, compareText: string): boolean {
    if (originalText.length == 0 || originalText.length != compareText.length) {
        // 如果傳入字串長度不同或空字串
        return false;
    }
    // 字母對應 Map
    let originalTextMap = new Map();
    let compareTextMap = new Map();

    for (let i = 0; i < originalText.length; i++) {
        // 取得比較的字母
        let originalLetter = originalText[i];
        let compareLetter = compareText[i];

        if ((originalTextMap.has(originalLetter) && originalTextMap.get(originalLetter) != compareLetter)
            || compareTextMap.has(compareLetter) && compareTextMap.get(compareLetter) != originalLetter) {
            // 如果「原始文字字母對應」已有「對應的字母」，且「對應的字母」與「比較的字母」不一樣
            // 如果「比較文字字母對應」已有「對應的字母」，且「對應的字母」與「原始的字母」不一樣
            // 表示這個不是 Isomorphic 字串
            return false;
        }

        // 設定字母對應表
        originalTextMap.set(originalLetter, compareLetter);
        compareTextMap.set(compareLetter, originalLetter);
    }

    return true;
};

參考資料