Isomorphic ຊ່ອຍແນ່


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ ເຟສບຸກ Intel
Hash ແຮກ string

Isomorphic ຊ່ອຍແນ່ - ໃຫ້ສອງ strings ພວກເຮົາ ຈຳ ເປັນຕ້ອງກວດເບິ່ງວ່າທຸກໆລັກສະນະຂອງຕົວອັກສອນເກີດຂື້ນ string1 ມີແຜນທີ່ທີ່ມີເອກະລັກສະເພາະຢູ່ໃນ string2. ສະຫລຸບແລ້ວ, ໃຫ້ກວດເບິ່ງວ່າມີແຜນທີ່ ໜຶ່ງ ຫາ ໜຶ່ງ ຫລືບໍ່.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ

str1 = "aab"

str2 =“ xxy”

ຜົນຜະລິດ

ທີ່ແທ້ຈິງ

ຄໍາອະທິບາຍ

ແຜນທີ່ 'x' ກັບ 'a' ແລະແຜນທີ່ 'y' ກັບ 'b'.

ສູດການຄິດໄລ່ ສຳ ລັບ Isomorphic Strings

ຄວາມຍາວຂອງສາຍ ໜຶ່ງ ແລະສອງຕ້ອງຄືກັນ.

ປະສົມລັກສະນະແຕ່ລະຕົວຂອງ string1. ເມື່ອພວກເຮົາພົບກັບຕົວລະຄອນເປັນຄັ້ງ ທຳ ອິດໃນ string1 ແລ້ວກວດເບິ່ງກະແສໄຟຂອງ string2. ຖ້າກະແສໄຟຟ້າ string2 ມີຢູ່ໃນແຜນທີ່ແລ້ວສົ່ງຄືນແຜນທີ່ບໍ່ຖືກຕ້ອງຂອງແຜນທີ່ຂອງ string1 ດ້ວຍ string2 ແລະ ໝາຍ ເອົາກະແສ 2 ຂອງທີ່ ກຳ ລັງປະຕິບັດ. ຖ້າພວກເຮົາບໍ່ໄດ້ພົບກັບຕົວລະຄອນດັ່ງກ່າວເປັນເທື່ອ ທຳ ອິດໃນ string1 ແລ້ວກວດເບິ່ງວ່າຮູບລັກສະນະກ່ອນ ໜ້າ ນີ້ຖືກແຕ້ມໃສ່ໂຕອັກສອນດຽວກັນຂອງ string2.

ລະຫັດ C ++ ສຳ ລັບ Isomorphic Strings

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

ລະຫັດ Java ສຳ ລັບ Isomorphic Strings

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

ກະສານອ້າງອີງ