Рубрики

Проверьте, являются ли две данные строки изоморфными друг другу

Две строки str1 и str2 называются изоморфными, если возможно сопоставление один к одному для каждого символа строки str1 на каждый символ строки str2. И все вхождения каждого символа в 'str1' отображаются на тот же символ в 'str2'

Примеры:

Input:  str1 = "aab", str2 = "xxy"
Output: True
'a' is mapped to 'x' and 'b' is mapped to 'y'.

Input:  str1 = "aab", str2 = "xyz"
Output: False
One occurrence of 'a' in str1 has 'x' in str2 and 
other occurrence of 'a' has 'y'.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простое решение состоит в том, чтобы рассмотреть каждый символ 'str1' и проверить, соответствуют ли все его вхождения одному и тому же символу в 'str2'. Временная сложность этого решения составляет O (n * n).

Эффективное решение может решить эту проблему за O (n) время. Идея состоит в том, чтобы создать массив для хранения отображений обработанных символов.

1) If lengths of str1 and str2 are not same, return false.
2) Do following for every character in str1 and str2
   a) If this character is seen first time in str1, 
      then current of str2 must have not appeared before.
      (i) If current character of str2 is seen, return false.
          Mark current character of str2 as visited.
      (ii) Store mapping of current characters.
   b) Else check if previous occurrence of str1[i] mapped
      to same character.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для проверки, являются ли две строки изоморфными
#include<bits/stdc++.h>

using namespace std;

#define MAX_CHARS 256

  
// Эта функция возвращает true, если str1 и str2 изоморфны

bool areIsomorphic(string str1, string str2)

{

  

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

  

    // Длина обеих строк должна быть одинаковой для одного к одному

    // переписка

    if (m != n)

      return false;

  

    // Отметить посещенные символы в str2

    bool marked[MAX_CHARS] = {false};

  

    // Для сохранения сопоставления каждого символа от str1 до

    // это из str2. Инициализируйте все записи карты как -1.

    int map[MAX_CHARS];

    memset(map, -1, sizeof(map));

  

    // Обрабатываем все символы по одному

    for (int i = 0; i < n; i++)

    {

        // Если текущий символ str1 виден первым

        // время в нем.

        if (map[str1[i]] == -1)

        {

            // Если текущий символ str2 уже

            // видно, однозначное отображение невозможно

            if (marked[str2[i]] == true)

                return false;

  

            // Пометить текущий символ str2 как посещенный

            marked[str2[i]] = true;

  

            // Сохраняем отображение текущих символов

            map[str1[i]] = str2[i];

        }

  

        // Если это не первое появление текущего

        // символ в str1, затем проверить, если предыдущий

        // внешний вид сопоставлен с тем же символом str2

        else if (map[str1[i]] != str2[i])

            return false;

    }

  

    return true;

}

  
// Драйвер программы

int main()

{

   cout << areIsomorphic("aab", "xxy") << endl;

   cout << areIsomorphic("aab", "xyz") << endl;

   return 0;

}

Джава

// Java-программа для проверки изоморфности двух строк

import java.io.*;

import java.util.*;

class Isomorphic

{

    static int size = 256;

      

    // Функция возвращает true, если str1 и str2 изоморфны

    static boolean areIsomorphic(String str1, String str2)

    {

        int m = str1.length();

        int n = str2.length();

          

        // Длина обеих строк должна быть одинаковой для одного к одному

        // переписка

        if(m != n)

            return false;

              

        // Отметить посещенные символы в str2

        Boolean[] marked = new Boolean[size];

        Arrays.fill(marked, Boolean.FALSE);

          

        // Для сохранения сопоставления каждого символа от str1 до

        // это из str2. Инициализируйте все записи карты как -1.

        int[] map = new int[size];

        Arrays.fill(map, -1);

          

        // Обрабатываем все символы по одному

        for (int i = 0; i < n; i++)

        {

            // Если текущий символ str1 виден первым

            // время в нем.

            if (map[str1.charAt(i)] == -1)

            {

                // Если текущий символ str2 уже

                // видно, однозначное отображение невозможно

                if (marked[str2.charAt(i)] == true)

                    return false;

  

                // Пометить текущий символ str2 как посещенный

                marked[str2.charAt(i)] = true;

  

                // Сохраняем отображение текущих символов

                map[str1.charAt(i)] = str2.charAt(i);

            }

  

            // Если это не первое появление текущего

            // символ в str1, затем проверить, если предыдущий

            // внешний вид сопоставлен с тем же символом str2

            else if (map[str1.charAt(i)] != str2.charAt(i))

            return false;

        }

  

        return true;

    }

    // драйверная программа

    public static void main (String[] args) 

    {

        boolean res = areIsomorphic("aab", "xxy");

        System.out.println(res);

      

        res = areIsomorphic("aab", "xyz");

        System.out.println(res);

    }

}

питон

# Программа Python для проверки, являются ли две строки изоморфными

MAX_CHARS = 256

  
# Эта функция возвращает true, если str1 и str2 изоморфны

def areIsomorphic(string1, string2):

    m = len(string1)

    n = len(string2)

  

    # Длина обеих строк должна быть одинаковой для одного к одному

    # корреспонденция

    if m != n:

        return False

  

    # Чтобы отметить посещенных символов в str2

    marked = [False] * MAX_CHARS

  

    # Хранить отображение каждого символа от str1 до

    # это из str2. Инициализировать все записи карты как -1

    map = [-1] * MAX_CHARS

  

    # Обрабатывать все символы один за другим

    for i in xrange(n):

  

        # если текущий символ str1 виден первым

        # время в нем.

        if map[ord(string1[i])] == -1:

  

            # если текущий символ st2 уже

            # видел, однозначное отображение невозможно

            if marked[ord(string2[i])] == True:

                return False

  

            # Пометить текущий символ str2 как посещенный

            marked[ord(string2[i])] = True

  

            # Хранить отображение текущих символов

            map[ord(string1[i])] = string2[i]

  

        # Если это не первое появление тока

        # символ в str1, затем проверьте, если предыдущий

        # внешний вид сопоставлен с тем же персонажем str2

        elif map[ord(string1[i])] != string2[i]:

            return False

  

    return True

  
# Драйверная программа

print areIsomorphic("aab","xxy")

print areIsomorphic("aab","xyz")

# Этот код предоставлен Bhavya Jain

C #

// C # программа для проверки, если два
// строки изоморфны

using System;

  

class GFG {

      

    static int size = 256;

      

    // Функция возвращает true, если str1

    // и str2 изоморфны

    static bool areIsomorphic(String str1, 

                              String str2)

    {

          

        int m = str1.Length;

        int n = str2.Length;

          

        // Длина обеих строк должна быть одинаковой

        // для переписки один на один

        if(m != n)

            return false;

              

        // Отметить посещенные символы в str2

        bool[] marked = new bool[size];

          

        for(int i = 0; i < size; i++)

            marked[i]= false;

          

          

        // Для сохранения сопоставления каждого символа

        // от str1 до str2 и

        // Инициализируем все записи карты как -1.

        int[] map = new int[size];

          

        for(int i = 0; i < size; i++)

            map[i]= -1;

      

        // Обрабатываем все символы по одному

        for (int i = 0; i < n; i++)

        {

              

            // Если текущий символ str1

            // видел в первый раз

            if (map[str1[i]] == -1)

            {

                  

                // Если текущий символ str2

                // уже видно, один

                // одно отображение невозможно

                if (marked[str2[i]] == true)

                    return false;

  

                // Отметить текущий символ

                // str2 как посещено

                marked[str2[i]] = true;

  

                // Сохраняем отображение текущих символов

                map[str1[i]] = str2[i];

            }

  

            // Если это не первое появление текущего

            // символ в str1, затем проверить, если предыдущий

            // внешний вид сопоставлен с тем же символом str2

            else if (map[str1[i]] != str2[i])

            return false;

        }

  

        return true;

    }

      

    // Код драйвера

    public static void Main () 

    {

        bool res = areIsomorphic("aab", "xxy");

        Console.WriteLine(res);

      

        res = areIsomorphic("aab", "xyz");

        Console.WriteLine(res);

    }

}

  
// Этот код предоставлен Sam007.

Выход:

1
0

Спасибо Гаураву и Уткаршу за предложенный выше подход.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проверьте, являются ли две данные строки изоморфными друг другу

0.00 (0%) 0 votes