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;
};

参考资料