Что здесь делает цикл for?

Сначала я пройдусь по предоставленному вами объяснению.

Сначала мы инициируем две карты (mapS и mapT).

Педантично инициализируем две карты.

Во-вторых, перебрать длину строки s. (Я думаю, мы можем предположить строка t имеет одинаковую длину? Эта часть не ясна.)

Ради этой задачи мы можем предположить, что t не меньше, чем s.

Мы проверяем, равен ли символ в s[i] t[i],

Нет. Это было бы s[i] == t[i].

и это также имеет существовать на карте. (вот где он разваливается для меня)

Нет. mapS[s[i]] равно 0, если мы никогда не сохраняли значение для s[i] в mapS.

Вот что на самом деле делает условие if:

• Он ищет s[i] в mapS, возвращая некоторое количество int — либо int, которое мы последний раз сохраняли для ключа s[i], либо 0, если мы никогда не сохраняли int для ключа s[i].

• Он ищет t[i] в mapT, возвращая некоторое количество int — либо int, которое мы последний раз сохраняли для ключа t[i], либо 0, если мы никогда не сохраняли int для ключа t[i].

• Если два int различны, это заставляет функцию вернуться раньше со значением false.

После этого я рассматриваю строку как перспективную и добавляю ее в карта.

Оно не смотрит вперед. Забегая вперед, будет что-то вроде s[i+1] или t[i+1]. Он сохраняет i+1 на обеих картах, но не «заглядывает вперед».

Затем мы возвращаемся, если у нас нет проблем.

Мы возвращаем true, если выходим из тела цикла, потому что i достигла длины s, ни разу не возвращаясь раньше.

Теперь извините, если я ошибаюсь, но согласно документации разве мы не должны сравнивать ключи здесь?

Какая документация?

Кроме того, кто-то упомянул, понимаю ли я изоморфность. Я не совсем. У меня есть общее представление.

Не очевидно, что здесь означает «изоморфный», но мы с этим разберемся.

Теперь я пройдусь по моему анализу этой функции.

Один из способов понять, что делает цикл, — начать с простого ввода и пройти цикл «вручную» столько раз, сколько необходимо. (Вы начинаете с простого ввода, поэтому вам не нужно повторять его слишком много раз!)

Давайте сосредоточимся на переменной mapS и посмотрим, что с ней делает цикл. Поскольку mapS индексируется с использованием элементов из s, нам нужно выбрать некоторую строку для s. Используем "abcab".

Программа обновляет mapS только одним оператором:

        mapS[s[i]] = i+1;

Теперь давайте пройдемся по циклу и посмотрим, как развивается mapS. Предположим пока, что условие if всегда ложно.

Итак, в начале тела цикла мы можем сказать: для каждого символа c в s.substr(0, i) (первые i символы s) mapS[c] на единицу больше, чем последний индекс c в s.substr(0, i).

Обратите внимание, что s.substr(0, i) — это пустая строка, когда i == 0.

Как я упоминал ранее, mapS возвращает 0 для любого ключа, который на самом деле не хранится на карте. Итак, давайте подумаем, что 0 означает «s.substr(0, i) не содержит c».

Имея это значение для 0, мы можем сказать, что в начале тела цикла для каждого cmapS[c] кодирует последний индекс c в s.substr(0, i) следующим образом:

• mapS[c] == 0 кодирует значение «c не находится в s.substr(0, i)».

• mapS[c] == x кодирует значение «x - 1 < i и s[x - 1] == c и s.substr(0, i) не содержит c с индексом большим, чем x - 1».

Поскольку mapT обновляется точно так же, как mapS, за исключением использования символов из t, мы можем сказать, что оно кодирует то же значение, что и mapS, но относительно t вместо s.

Теперь мы готовы проанализировать условие оператора if: mapS[s[i]] != mapT[t[i]].

Помните, что s.substr(0, i) не достигает s[i]; он останавливается прямо перед s[i]. То есть "abcab"[2] есть 'c', а "abcab".substr(0, 2) есть "ab"; подстрока не заканчивается на 'c'.

Итак, в условии if:

• mapS[s[i]] — это закодированный последний индекс s[i] в s.substr(0, i). (Помните, что «закодированный последний индекс» может кодировать значение «нет такого индекса».)

• mapT[t[i]] — это закодированный последний индекс t[i] в t.substr(0, i).

Таким образом, оператор if заставляет функцию вернуться раньше со значением false, если эти закодированные последние индексы различаются.

Теперь предположим, что цикл доходит до i == s.length(), а условие if никогда не выполняется. Затем цикл завершается нормально, и программа доказывает, что каждый раз, когда она встречала какой-то символ c в s и какой-то соответствующий символ d по тому же индексу в t, она ранее видела c и d с одинаковыми более ранними (закодированными) индексами в s и t.

Это небольшой скачок, чтобы перейти от этого к более целостному пониманию isIsomorphic, но вот что isIsomorphic(s, t) означает:

Есть ли способ единообразно сопоставить каждый символ c, который появляется в s, с уникальным символом d, который появляется в t? И наоборот? Если это так, isIsomorphic(s, t) возвращает true. В противном случае возвращается ложь.

Рассмотрим этот пример: isIsomorphic("abcab", "zyxzy"). Он возвращает true, потому что между символами, встречающимися в s, и символами, встречающимися в t, существует однородное двунаправленное сопоставление:

Но isIsomorphic("abcab", "zyzzy") неверно. И 'a', и 'c' в s должны сопоставляться с 'z' в t, но 'z' в t может сопоставляться только с одним символом, а не с 'a' и 'c' одновременно.

Такое универсальное, уникальное двунаправленное отображение называется биекцией.

Изоморфизм всегда является биекцией, но обычно имеет дополнительные требования, в зависимости от типа структур, на которых он определен. Например, в теории графов вы можете определить взаимное соответствие между узлами двух графов, но изоморфизм также должен определить взаимное соответствие между ребрами этих графов.

Лучшее название для этой функции может быть bijectionExists или samePattern.

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

Две строки изоморфны, если каждому символу строки A можно сопоставить каждый символ строки B.

Например, ACAB и XCXY изоморфны.

A -> X
C -> C
B -> Y

И еще, ACAB и XCZY не изоморфны.

A -> X, Z  # 'A' cannot map to multiple characters
C -> C
B -> Y

Итак, как код решает это? Мы рассмотрим части тела функции.

std::map<char, int> mapS;
std::map<char, int> mapT;

Объявите две карты, по одной для каждой строки. Они оба пусты.

for(int i = 0; i < s.length(); i++)

Этот цикл заботится только о длине s, и мы уже столкнулись с препятствием. Если бы мы хотели проверить одностороннее отображение, где s -> t, но t !-> s, эта функция сделала бы это неправильно. Я бы пошел дальше и сказал, что если длины s и t различны, функция должна немедленно вернуть false. Потому что мы гарантированно читаем за пределы, если t.length() < s.length().

Двигаемся дальше:

{
    if (mapS[s[i]] != mapT[t[i]]) return false;

    mapS[s[i]] = i+1;
    mapT[t[i]] = i+1;
}

Мы должны взять их вместе. Проверка if просто хочет знать, имеют ли соответствующие элементы карты одинаковое значение. Если это не так, у нас есть несоответствие в нашем сопоставлении, и мы можем немедленно вернуть false. Если значения совпадают, мы обновляем обе карты вместе. i + 1 используется из-за того, как operator[] работает с картами. Если ключ не существует, попытка индексации с помощью этого ключа создаст запись на карте и инициализирует значение int равным 0. Добавление 1 — это дешевый способ обойти ложные срабатывания.

Наконец, если вы пройдете цикл без возврата false, предполагается, что строки изоморфны, и вы вернете true.

Но эта функция фиктивная. Можно почти сказать, что он проверяет «односторонний» изоморфизм, когда t длиннее, чем s, но если s длиннее, он все равно может возвращать true и при этом вызывать неопределенное поведение.

Для меня лучшим решением является сохранение фактического отображения символов. Вам также необходимо отслеживать уникальные символы во второй строке. И первая проверка должна быть на одинаковую длину.

#include <iostream>
#include <set>
#include <string>
#include <unordered_map>

class Solution {
 public:
  bool isIsomorphic(const std::string& s, const std::string& t) {
    if (s.length() != t.length()) return false;

    // The map stores the character mapping from s to t. Characters in s
    // are the key, and the value is the corresponding character in t.
    std::unordered_map<char, char> map;

    // The set stores the **unique** characters of t. This allows us to know
    // if we already have a mapping to a character in t, if it exists in
    // the set.
    std::set<char> trackedChars;

    for (std::size_t i = 0; i < s.length(); ++i) {
      char sChar = s[i];
      char tChar = t[i];

      // Have I mapped this character yet?
      if (map.find(sChar) != map.end()) {  // Yes
        // Is the mapping still correct?
        if (map[sChar] != tChar) {  // Map mismatch found
          return false;
        }
      } else {  // No
        // Has the corresponding character been mapped already?
        if (trackedChars.find(tChar) != trackedChars.end()) {
          // tChar is already mapped
          return false;
        } else {  // tChar is also not yet mapped
          map[sChar] = tChar;
          trackedChars.insert(tChar);
        }
      }
    }

    // Making it out of the loop implies every character mapped correctly.
    return true;
  }
};

int main() {
  std::string one{"ACAB"};
  std::string two{"XCXY"};

  Solution s;
  std::cout << std::boolalpha << s.isIsomorphic(one, two) << '\n';
}

Выход:

true

Не хочу нагромождать сказанное, но для класса такая структура кода — мусор. Это должна быть просто бесплатная функция или, может быть, вставленная в пространство имен. Но это выходит за рамки этого вопроса.