同構字符串Leetcode解決方案  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 Facebook 谷歌 英特爾 LinkedIn Microsoft微軟 神諭 雅虎
算法 編碼 哈希圖 訪問 面試準備 力碼 力碼解決方案

問題陳述  

在這個問題上,我們得到兩個 字符串,a和b。 我們的目標是判斷兩個字符串是否同構。

當且僅當第一個字符串中的字符在出現的所有點處都可以被任何字符(包括其自身)替換,同時保持字符的相對順序相同時,這兩個字符串才稱為同構。 沒有兩個字符可以映射到同一字符。

s = "abb"  , t = "cdd"
true
s = "Google" , t = "123456"
false

同構字符串Leetcode解決方案

途徑  

我們可以使用哈希圖來保存第一個字符串中每個字符的替換。 如果我們到達一個可以替換第一個字符的位置,

  • 我們可以檢查替換項是否與另一個字符串中的字符相同。 如果不是,則字符串不能是同構的。
  • 如果沒有替換第一個字符,我們可以檢查第二個字符是否已被替換為第一個字符串中的任何其他字符。 此檢查很重要,因為我們需要將第一個字符串中的每個字符映射到一個唯一字符。 如果不存在替換為第二個字符的字符,我們可以將第二個字符指定為第一個字符的替換。 否則,字符串不是同構的。
也可以看看
插入間隔Leetcode解決方案

算法

  1. 初始化一個 字符字符 哈希圖 替代 字符布爾 哈希圖
  2. 迭代字符串中的每個字符 st:
    • If 替代 包含 s [i] 作為一個關鍵:
      • If 替換[s [i]]!= t [i]
        • 返回假
    • 別的:
      • If used [t [i]] == true
        • 返回假
      • Wi-Fi: 替換[s [i]] = t [i]
      • Wi-Fi: used [t [i]] = true
  3. 返回真

同構字符串Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>

using namespace std;

bool isIsomorphic(string s , string t) {
    int n = s.length();

    unordered_map <char , char> replacement;
    unordered_map <char , bool> used;

    for(int i = 0 ; i < n ; i++)
    {
        if(replacement.count(s[i]))
        {
            if(replacement[s[i]] != t[i])
                return false;
        }
        else
        {
            if(used[t[i]])
                return false;
            replacement[s[i]] = t[i];
            used[t[i]] = true;
        }
    }

    return true;
}

int main() {
    string s = "abb" , t = "cdd";
    cout << (isIsomorphic(s , t) ? "true" : "false") << endl;
    return 0;
}

Java程序

import java.util.*;

class isomorphic_string {
    public static void main(String args[]) {
        String s = "abb" , t = "cdd";
        System.out.println(isIsomorphic(s , t) ? "true" : "false");
    }

    public static boolean isIsomorphic(String s , String t) {
        HashMap <Character , Character> replacement = new HashMap <>();
        HashMap <Character , Boolean> used = new HashMap <>();

        for(int i = 0 ; i < s.length() ; i++) {
            if(replacement.containsKey(s.charAt(i))) {
                if(replacement.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else {
                if(used.containsKey(t.charAt(i)))
                    return false;
                replacement.put(s.charAt(i) , t.charAt(i));
                used.put(t.charAt(i) , true);
            }
        }

        return true;
    }
}
true

同構字符串Leetcode解的複雜性分析

時間複雜度

O(N),N =字符串s和t的長度。

空間複雜度 

O(1), 因為在輸入中將有恆定數量的唯一字符。

1