इसोमोर्फिक स्ट्रिंग्स


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन एप्पल फेसबुक Intel
हैश ह्याशिंग घागो

इसोमोर्फिक स्ट्रिंगहरू - दुई दिइयो तार हामीले जाँच गर्न आवश्यक छ कि क्यारेक्टरको हरेक घटनाको लागि string1 भित्र वर्णहरूको साथ एक अद्वितीय म्यापि। छ string2। संक्षेपमा, जाँच गर्नुहोस्, यदि त्यहाँ एकलाई एक म्यापि। छ वा छैन।

उदाहरणका

आगत

str1 = "aab"

str2 = "xxy"

उत्पादन

साँचो

स्पष्टीकरण

'a' को साथ नक्सा 'x' र 'b' को साथ नक्शा 'y'।

Isomorphic स्ट्रिंगहरूको लागि एल्गोरिथ्म

एक र दुई स्ट्रि ofको लम्बाई एक हुनुपर्दछ।

स्ट्रि1 १ को प्रत्येक क्यारेक्टर लाई इटरेट गर्नुहोस्। जब हामी स्ट्रिंग १ मा पहिलो पटक क्यारेक्टर भेट्छौं भने स्ट्रिंग २ को हालको जाँच गर्नुहोस्। यदि स्ट्रिंग २ को हालको नक्शा मा पहिले नै अवस्थित छ भने स्ट्रिंग २ का साथ स्ट्रिंग १ को नक्सा हालको फिर्ती फर्काउनुहोस् र स्ट्रिंग २ को वर्तमानलाई लेखाएको रूपमा चिन्ह लगाउनुहोस्। यदि हामीले स्ट्रिंग १ मा पहिलो पटक क्यारेक्टरको सामना गरेनौं भने जाँच गर्नुहोस् कि यदि अघिल्लो उपस्थिति स्ट्रिंग २ को समान वर्णमा म्याप गरिएको छ भने।

सी ++ ईसोमोर्फिक स्ट्रिंगहरूको लागि कोड

// 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 स्ट्रिंगहरूको लागि जाभा कोड

// 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

संदर्भ