פתרון Leetcode מיתרים איזומורפיים


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג פייסבוק Google אינטל לינקדין מיקרוסופט אורקל יאהו
מפת גיבוב מחרוזת

הצהרת בעיה

בבעיה זו נותנים לנו שניים מחרוזות, a ו- b. המטרה שלנו היא לדעת אם שני המיתרים הם איזומורפיים או לא.

שני מחרוזות נקראים איזומורפיים אם ורק אם ניתן להחליף את התווים במחרוזת הראשונה בכל תו (כולל עצמו) בכל נקודות התרחשותו תוך שמירה על הסדר היחסי של התווים זהה. אין שתי דמויות שיכולות למפות לאותה תו.

דוגמה

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

פתרון Leetcode מיתרים איזומורפיים

גישה

אנו יכולים להשתמש ב- hashaps כדי לשמור את ההחלפה לכל תו במחרוזת הראשונה. אם נגיע למצב שיש תחליף לדמות הראשונה,

  • אנו יכולים לבדוק אם ההחלפה זהה לדמות במחרוזת השנייה. אם לא, המיתרים לא יכולים להיות איזומורפיים.
  • במקרה שאין תחליף לדמות הראשונה, נוכל לבדוק אם התו השני שימש כתחליף לכל תו אחר במחרוזת הראשונה. בדיקה זו חשובה מכיוון שעלינו למפות כל תו במחרוזת הראשונה לדמות ייחודית. אם אין דמות שהחלפתה היא התו השני, נוכל להקצות את הדמות השנייה כמחליפה של הדמות הראשונה. אחרת, המיתרים אינם איזומורפיים.

אַלגוֹרִיתְם

  1. אתחל א אופי ל אופי מפת גיבוב תַחֲלִיף וכן אופי ל בוליאני מפת גיבוב מְשׁוּמָשׁ
  2. חזר על כל דמות במחרוזת s ו t:
    • If תַחֲלִיף מכיל סִי] כמפתח:
      • If החלפה [s [i]]! = t [i]
        • להחזיר כוזב
    • אַחֵר:
      • If השתמשו ב- [t [i]] == נכון
        • להחזיר כוזב
      • סט החלפה [s [i]] = t [i]
      • סט בשימוש [t [i]] = נכון
  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), כיוון שיהיה מספר קבוע של תווים ייחודיים בקלט.