Определите, близки ли две строки

Средняя
medium , string , hash table
22 March 2024

Описание задачи #

Вам дано две строки. Верните true, если обе строки являются близкими, и false в противном случае.

Две строки считаются близкими, если одну из другой можно получить с помощью следующих операций.

Операция 1: Поменяйте местами любые два существующих символа (swap). Например, abcde -> aecdb (букву b поменяли местами с буквой e).

Операция 2: Преобразуйте каждое появление одного существующего символа в другой существующий символ и сделайте то же самое с другим символом. Например, aacabb -> bbcbaa (все буквы a превращаются в буквы b, а все буквы b превращаются в буквы a).

Вы можете использовать операции с любой строкой столько раз, сколько необходимо.

Ограничения #

Примеры #

  • Входные данные: word1 = "abc", word2 = "bca"

    Ответ: true]

    Объяснение

    Вы можете получить word1 из word2 за 2 операции.

    • Примените операцию 1: «abc» -> «acb»
    • Примените операцию 1: «acb» -> «bca»

  • Входные данные: word1 = "a", word2 = "aa"

    Ответ: false

    Объяснение

    Невозможно получить word2 из word1 или наоборот за любое количество операций.

  • Входные данные: word1 = "cabbba", word2 = "abbccc"

    Ответ: true

    Объяснение

    Вы можете получить word1 из `word2 за 3 операции.

    • Примените операцию 1: «cabbba» -> «caabbb»
    • Примените операцию 2: «caabbb» -> «baaccc»
    • Примените операцию 2: «baaccc» -> «abbccc»

Решение #

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

В первую очередь нужно внимательно посмотреть на примеры из задачи, а именно на третий пример. Точнее даже на состояния первой строки при переходе во вторую. Для удобства, разместим их в столбик и посчитаем частоту каждой буквы в слове.

cabbba — 1с, 2a, 3b
caabbb — 1c, 2a, 3b
baaccc — 1b, 2a, 3c
abbccc — 1a, 2b, 3c

При внимательном рассмотрении можно заметить, что при преобразовании строки, меняются буквы, но цифры частот остаются неизменными. Назовем это сигнатурой частоты букв в слове. То есть независимо от преобразований в слове всегда сохраняется следующая сигнатура частот — [1, 2, 3].

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

  1. Сигнатура частоты букв в обоих словах должна быть одинаковой.
  2. Все буквы из первого слова должны присутствовать во втором слове и наоборот.

Во всех противных случаях строки не являются близкими.

Отсюда следует, что для решения задачи нам потребуется завести 2 счетчика для подсчета частоты каждой из букв в обеих словах. После подсчета у нас получатся два набора частот.

{
	"c": 1,
	"a": 2,
	"b": 3
}

{
	"c": 3,
	"a": 1,
	"b": 2
}

Теперь нам остается сравнить эти частоты:

  1. В наборах должно быть одинаковое количество ключей и их состав должен совпадать
  2. В наборах должны быть одинаковые значения (вне зависимости от ключей)

Чтобы оптимизировать сверку значений можно ввести вспомогательную хеш-мапу, у которой в качестве ключа будет частота (значения из наших счетчиков), а в качестве значения - счетчик. При проходе по первому набору мы будем увеличивать наш счетчик, а при проходе по второму — уменьшать. Если в итоге все счетчики окажутся равными нулю, значит набор частот в наборах одинаковый.

Таким образом, после того как мы проитерируемся по первому набору, мы получим такое промежуточное состояние вспомогательных счетчиков:

{
	1: 1,
	2: 1,
	3: 1
}

После итерации по второму набору мы получим следующее итоговое состояние вспомогательных счетчиков:

{
	1: 0,
	2: 0,
	3: 0
}

Для оптимизации мы можем сделать и инкремент и декремент в рамках одного цикла, так как набор ключей должен быть одинаковым.

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

Реализация #

  • package two_close_strings

func closeStrings(word1 string, word2 string) bool {
	if len(word1) != len(word2) {
		return false
	}

	counter1 := make(map[rune]int)
	counter2 := make(map[rune]int)

	for _, char := range word1 {
		counter1[char]++
	}

	for _, char := range word2 {
		counter2[char]++
	}

	tempCounter := make(map[int]int)

	for k, v := range counter1 {
		v2, exist := counter2[k]
		if !exist {
			return false
		}

		tempCounter[v]++
		tempCounter[v2]--
	}

	for _, count := range tempCounter {
		if count != 0 {
			return false
		}
	}

	return true
}

  • const fillCounter = (word: string): Record<string, number> => {
    const counter: Record<string, number> = {}

    for (let i = 0; i < word.length; i++) {
        if (!counter[word[i]]) {
            counter[word[i]] = 0
        }
        counter[word[i]]++
    }

    return counter
}

export const closeStrings = (word1: string, word2: string): boolean => {
    if (word1.length !== word2.length) {
        return false
    }

    const counter1 = fillCounter(word1)
    const counter2 = fillCounter(word2)
    const tempCounter: Record<number, number> = {}

    for (const [k, v] of Object.entries(counter1)) {
        const v2 = counter2[k]

        if (!v2) {
            return false
        }

        if (!tempCounter[v]) {
            tempCounter[v] = 0
        }
        if (!tempCounter[v2]) {
            tempCounter[v2] = 0
        }

        tempCounter[v]++
        tempCounter[v2]--
    }

    for (const [_, count] of Object.entries(tempCounter)) {
        if (count !== 0) {
            return false
        }
    }

    return true
}

Оценка сложности #

По времени

Для формирования частот букв мы дважды итерируемся по каждому слову, то есть выполняем 2n операций, где n — длина слова. Кроме того мы дважды итерируемся по частотам, но эту сложность можно считать константной, так как количество букв в английском алфавите фиксировано. Таким образом сложность по времени линейная O(n).

По памяти

Сложность по памяти константная O(1). Хоть мы и выделяем память для хранения мап, но они имеют фиксированный размер, так как в английском алфавите всего 26 букв. Таким образом выделение дополнительной памяти можно считать константным.

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >