JavaScript 检查两个给定的字符串是否同构的方法

如果可以将第一个字符串的每个字符映射到第二个字符串的每个字符，那么这两个字符串被认为是同构的。基本上，在同构字符串中，第一个字符串的每个字符与第二个字符串的每个字符之间存在一对一的映射关系。我们也可以说，第一个字符串的每个字符都被第二个字符串的每个字符替代。

示例 1：

str1 = 'ABCA'  
str2 = 'XYZX'  
'A' maps to 'X'  
'B' maps to 'Y'  
'C' maps to 'Z'  

在这里，第一个字符串的每个字符都可以映射到第二个字符串的每个字符。所以str1和str2是同构的。

示例2：

str1 = 'ABCA'  
str2 = 'WXYZ'  
'A' maps to 'W'  
'B' maps to 'X'  
'C' maps to 'Y'  
'A' again maps to 'Z'  

这两个字符串不是同构的，因为第一个字符串中的字符’A’与第二个字符串中的两个字符映射。

我们可以用两种方法在Javascript中检查给定的两个字符串是否同构：

• 使用朴素方法
• 使用哈希映射

方法1：使用原生方法

在这种方法中，我们将比较第一个字符串的每个字符与第二个字符串的另一个字符，同样比较第二个字符串。两个字符串的当前字符不应等于其他字符。这种方法的时间复杂度为O(N^2)，其中n是字符串的长度。这是一种暴力的方法，效率不高。

以下是上述方法的实现。

Javascript

function isStringIsomorphic(str1, str2) {
    if (str1.length !== str2.length) {
        return false;
    }
    for (let i = 0; i < str1.length; i++) {
        for (let j = i + 1; j < str1.length; j++) {
            if (
                (str1[i] === str1[j] && 
                str2[i] !== str2[j]) ||
                (str1[i] !== str1[j] && 
                str2[i] === str2[j])
            ) {
                return false;
            }
        }
    }
    return true;
}
 
str1 = "ABCA";
str2 = "XYZX";
console.log(isStringIsomorphic(str1,str2));

输出

true

方法2： 使用哈希映射

要检查字符串是否同构，我们需要注意以下条件：

• 两个字符串的长度应该相等
• 两个字符串当前的字符不能与其他字符映射

我们将使用一个 哈希映射 来存储从 str1 到 str2 的字符映射。我们还将使用一个 集合 来存储 str2 中已经映射的字符。

下面是上述方法的实现。

Javascript

// JavaScript program for above approach
 
// Function to check isomorphic strings
function isIsomorphic(str1, str2) {
 
    // If length of strings are not equal then 
    // they are not isomorphic
    if (str1.length !== str2.length) {
        return false;
    }
 
    // Map to store the mapping between 
    // characters of first string to second
    const map = new Map();
 
    // Set to store the already mapped
    // character of second string
    const set = new Set();
 
    for (let i = 0; i < str1.length; i++) {
 
        // Taking ith char from both strings
        char1 = str1.charAt(i);
        char2 = str2.charAt(i);
 
        // If char1 has already been mapped
        if (map.has(char1) == true) {
 
            // Then we have to check that 
            // mapped char should be same
            if (map.get(char1) !== char2) {
                return false;
            }
        }
 
        // If char1 is appearing for the first time
        else {
 
            // Check in the set that the char2
            // is already there or not
            if (set.has(char2)) {
                return false;
            }
 
            // If none of above condition is true
            // it means both char1 and char2 are 
            // appearing for the first time
            // insert them into the map
            map.set(char1, char2);
            set.add(char2);
        }
    }
    return true;
}
str1 = "ABCA";
str2 = "XYZX";
console.log(isIsomorphic(str1, str2));

输出

true