Изоморфни струни Leetcode решение  


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Bloomberg Facebook Google Intel LinkedIn Microsoft Оракул Yahoo
алгоритми кодиране HashMap Интервю интерпретация LeetCode LeetCodeSolutions Низ

Декларация за проблема  

В този проблем ни дават две струни, a и b. Нашата цел е да кажем дали двата струна са изоморфни или не.

Две низове се наричат ​​изоморфни, ако и само ако символите в първия низ могат да бъдат заменени с който и да е символ (включително себе си) във всички точки на появата му, като същевременно се запази относителният ред на символите еднакъв. Не могат два символа да се съпоставят с един и същ знак.

Пример

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

Изоморфни струни Leetcode решение

Подход  

Можем да използваме hashmaps, за да запазим заместването на всеки символ в първия низ. Ако достигнем позиция, при която има заместител на първия знак,

  • Можем да проверим дали заместването е същото като символа в другия низ. Ако не, низовете не могат да бъдат изоморфни.
  • В случай че няма замяна на първия символ, можем да проверим дали вторият знак е бил използван като заместител на който и да е друг знак в първия низ. Тази проверка е важна, тъй като трябва да съпоставим всеки символ от първия низ с уникален символ. Ако не съществува символ, чийто заместител е вторият знак, можем да присвоим втория знак като заместител на първия символ. В противен случай струните не са изоморфни.

алгоритъм

  1. Инициализирайте a характер да се характер hashmap замяна и характер да се булева hashmap използва
  2. Итерирайте за всеки символ в низа s и t:
    • If замяна съдържа s [i] като ключ:
      • If заместване [s [i]]! = t [i]
        • връщане фалшиви
    • В противен случай:
      • If използвано [t [i]] == true
        • връщане фалшиви
      • определен заместване [s [i]] = t [i]
      • определен използвано [t [i]] = true
  3. Връщане вярно
Вижте също
Вмъкнете Interval Leetcode Solution

Внедряване на изоморфни низове Leetcode Solution

Програма 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), тъй като във входа ще има постоянен брой уникални символи.