Isomorphic ညှို့  


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Apple Facebook က Intel က
hash တားဆီးခြင်း ကြိုး

Isomorphic Strings - နှစ်ခုပေး ညှို့ ကျွန်တော်တစ် ဦး ဇာတ်ကောင်အမှုအမျိုးမျိုးရှိသမျှဖြစ်ပျက်မှုရှိမရှိစစ်ဆေးဖို့လိုအပ်ပါတယ် string1 ဇာတ်ကောင်တွေနဲ့ထူးခြားတဲ့မြေပုံရှိတယ် string2။ အတိုချုပ်ဆိုရလျှင်မြေပုံတစ်ခုမှတစ်ခုသို့မဟုတ်ရှိမရှိစစ်ဆေးပါ။

နမူနာ  

input

str1 =“ aab”

str2 = "xxy"

output

စစ်မှန်သော

ရှင်းလင်းချက်

'a' နှင့် 'x' ကို 'b' နှင့် 'y' ကိုပြပါ။

Isomorphic ညှို့များအတွက် Algorithm  

string တစ်ခုနှင့်နှစ်အရှည်အတူတူဖြစ်ရပါမည်။

string1 တစ်ခုချင်းစီကိုအက္ခရာတင်ပါ။ string1 ထဲကပထမဆုံးအကြိမ်အနေနဲ့ character ကိုတွေ့ရင် string2 ရဲ့ current ကိုစစ်ဆေးပါ။ string2 ၏ current သည်မြေပုံတွင်ရှိပြီးဖြစ်ပါက string1 ၏မှားယွင်းသောအခြား map map ကို string2 နှင့်အတူပြန်ယူပါ။ string2 ထဲကပထမဆုံးအကြိမ်အနေနဲ့စာလုံးကိုမတွေ့ခဲ့ဘူးဆိုရင်အရင်ပုံစံဟာ string1 ရဲ့တူညီတဲ့ character နဲ့ဆက်စပ်မှုရှိမရှိစစ်ဆေးပါ။

Isomorphic Strings အတွက် C ++ code  

// C++ program to check if two strings are isomorphic 
#include<bits/stdc++.h> 
using namespace std; 
#define MAX_CHARS 256 

// This function returns true if str1 and str2 are ismorphic 
bool areIsomorphic(string str1, string str2) 
{ 

  int m = str1.length(), n = str2.length(); 

  // Length of both strings must be same for one to one 
  // corresponance 
  if (m != n) 
  return false; 

  // To mark visited characters in str2 
  bool marked[MAX_CHARS] = {false}; 

  // To store mapping of every character from str1 to 
  // that of str2. Initialize all entries of map as -1. 
  int map[MAX_CHARS]; 
  memset(map, -1, sizeof(map)); 

  // Process all characters one by on 
  for (int i = 0; i < n; i++) 
  { 
    // If current character of str1 is seen first 
    // time in it. 
    if (map[str1[i]] == -1) 
    { 
      // If current character of str2 is already 
      // seen, one to one mapping not possible 
      if (marked[str2[i]] == true) 
        return false; 

      // Mark current character of str2 as visited 
      marked[str2[i]] = true; 

      // Store mapping of current characters 
      map[str1[i]] = str2[i]; 
    } 

    // If this is not first appearance of current 
    // character in str1, then check if previous 
    // appearance mapped to same character of str2 
    else if (map[str1[i]] != str2[i]) 
      return false; 
  } 

  return true; 
} 

// Driver program 
int main() 
{ 
cout << areIsomorphic("aab", "xxy") << endl; 
cout << areIsomorphic("aab", "xyz") << endl; 
return 0; 
} 

Isomorphic Strings အတွက် Java code  

// Java program to check if two strings are isomorphic 
import java.io.*; 
import java.util.*; 
class Isomorphic 
{ 
  static int size = 256; 
  
  // Function returns true if str1 and str2 are ismorphic 
  static boolean areIsomorphic(String str1, String str2) 
  { 
    int m = str1.length(); 
    int n = str2.length(); 
    
    // Length of both strings must be same for one to one 
    // corresponance 
    if(m != n) 
      return false; 
      
    // To mark visited characters in str2 
    Boolean[] marked = new Boolean[size]; 
    Arrays.fill(marked, Boolean.FALSE); 
    
    // To store mapping of every character from str1 to 
    // that of str2. Initialize all entries of map as -1. 
    int[] map = new int[size]; 
    Arrays.fill(map, -1); 
    
    // Process all characters one by on 
    for (int i = 0; i < n; i++) 
    { 
      // If current character of str1 is seen first 
      // time in it. 
      if (map[str1.charAt(i)] == -1) 
      { 
        // If current character of str2 is already 
        // seen, one to one mapping not possible 
        if (marked[str2.charAt(i)] == true) 
          return false; 

        // Mark current character of str2 as visited 
        marked[str2.charAt(i)] = true; 

        // Store mapping of current characters 
        map[str1.charAt(i)] = str2.charAt(i); 
      } 

      // If this is not first appearance of current 
      // character in str1, then check if previous 
      // appearance mapped to same character of str2 
      else if (map[str1.charAt(i)] != str2.charAt(i)) 
      return false; 
    } 

    return true; 
  } 
  // driver program 
  public static void main (String[] args) 
  { 
    boolean res = areIsomorphic("aab", "xxy"); 
    System.out.println(res); 
  
    res = areIsomorphic("aab", "xyz"); 
    System.out.println(res); 
  } 
}
1
0

အညွှန်း

လည်းကြည့်ရှုပါ
ထူးခြားသော Paths Leetcode Solution