Isomorphic Strings Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም ብሉምበርግ ፌስቡክ google Intel LinkedIn የ Microsoft በ Oracle ያሁ
ሃሽ ማፕ ሕብረቁምፊ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ ሁለት ተሰጠን ሕብረቁምፊዎች፣ ሀ እና ለ ግባችን ሁለቱ ሕብረቁምፊዎች isomorphic ወይም አለመሆኑን መለየት ነው።

ሁለት ሕብረቁምፊዎች isomorphic ተብለው ይጠራሉ እና በአንደኛው ሕብረቁምፊ ውስጥ ያሉት ገጸ-ባህሪያቶች በአንጻራዊነት ተመሳሳይ ቅደም ተከተላቸውን ጠብቀው በሚኖሩባቸው በሁሉም ቦታዎች በማንኛውም ባህሪ (እራሱንም ጨምሮ) መተካት ከቻሉ ብቻ ፡፡ ወደ ተመሳሳዩ ቁምፊ ሁለት ቁምፊዎች ካርታ ማድረግ አይችሉም ፡፡

ለምሳሌ

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

Isomorphic Strings Leetcode መፍትሔ

ቀረበ

በመጀመሪያው ሕብረቁምፊ ውስጥ ለእያንዳንዱ ቁምፊ ምትክ ለማስቀመጥ ሃሽማዎችን መጠቀም እንችላለን ፡፡ ለመጀመሪያው ገጸ-ባህሪ ምትክ የሚሆንበት ቦታ ላይ ከደረስን ፣

  • ምትክ በሌላኛው ሕብረቁምፊ ውስጥ ካለው ቁምፊ ጋር ተመሳሳይ መሆኑን ማረጋገጥ እንችላለን ፡፡ ካልሆነ ግን ሕብረቁምፊዎች isomorphic ሊሆኑ አይችሉም ፡፡
  • ለመጀመሪያው ቁምፊ ምትክ ከሌለ ፣ ሁለተኛው ቁምፊ በመጀመሪያው ሕብረቁምፊ ውስጥ ለሌላ ማንኛውም ገጸ-ባህሪ ምትክ ሆኖ ጥቅም ላይ እንደዋለ ማረጋገጥ እንችላለን ፡፡ ይህ ቼክ አስፈላጊ ነው ምክንያቱም በመጀመሪያው ሕብረቁምፊ ውስጥ ያሉትን እያንዳንዱን ገጸ-ባህሪ ወደ ልዩ ገጸ-ባህሪ ማረም ያስፈልገናል ፡፡ የእሱ ምትክ ሁለተኛው ገጸ-ባህሪ ያለው ገጸ-ባህሪ ከሌለው እንደ ሁለተኛው ገጸ-ባህሪ ምትክ ሁለተኛውን ገጸ-ባህሪ ልንመድበው እንችላለን ፡፡ አለበለዚያ ሕብረቁምፊዎች isomorphic አይደሉም ፡፡

አልጎሪዝም

  1. ማስጀመር ሀ ባለታሪክ ወደ ባለታሪክ ሃሽፕ መተካት እና ባለታሪክ ወደ ቡሊያን ሃሽፕ ጥቅም ላይ የዋለው
  2. በሕብረቁምፊ ውስጥ ላለ እያንዳንዱ ቁምፊ ኢተሬትድ st:
    • If መተካት ያካትታል s [i] እንደ ቁልፍ
      • If መተካት [s [i]]! = t [i]
        • ሐሰት መመለስ
    • ሌላ
      • If ያገለገለ [t [i]] == እውነት ነው
        • ሐሰት መመለስ
      • ስብስብ መተካት [s [i]] = t [i]
      • ስብስብ ያገለገለ [t [i]] = እውነት ነው
  3. ወደ እውነት ተመለስ

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

የጃቫ ፕሮግራም

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

Isomorphic string Leetcode መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ኤን = የሕብረቁምፊዎች ርዝመት s እና t.

የቦታ ውስብስብነት 

ኦ (1) ፣ በግብአት ውስጥ የማያቋርጥ ልዩ ቁምፊዎች ብዛት ስለሚኖር።