Участник:Alvant/TaskKSimilarStrings

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/k-similar-strings/

Иногда падает на последних тестах (всего 54 теста на сайте). Но если несколько раз перезапустить, то в итоге пройдёт :)

Зато сложность по времени тут не очень большая: O(N * W), где N — длина строки, W — количество символов в алфавите. На самом деле сложность O(N * \binom{W}{2}), но в задаче в алфавите всего 6 букв. Хотя N тоже сильно ограничено: не больше 20.

from typing import Tuple, List
 
class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        if len(A) != len(B):
            raise ValueError()
 
        if sorted(A) != sorted(B):
            raise ValueError()
 
        if len(A) == 0:
            return 0
 
        if A == B:
            return 0
 
        A, B = self.pop_same_letters(A, B)
 
        result_k = 0
 
        cycles = self.find_cycles(A, B)
 
        while len(cycles) > 0:
            original_num_cycles = len(cycles)
 
            min_cycle_length = min([len(c) for c in cycles])
            min_cycle = [c for c in cycles if len(c) == min_cycle_length][0]  # TODO: sometimes may choose wrong cycle here?
            A = self.swap_for_cycle(A, min_cycle)
 
            result_k += len(min_cycle) - 1
 
            A, B = self.pop_same_letters(A, B)
            cycles = self.find_cycles(A, B)
 
        return result_k
 
    def pop_same_letters(self, A: str, B: str) -> Tuple[str, str]:
        new_A = ''.join([a for i, a in enumerate(A) if B[i] != a])
        new_B = ''.join([b for i, b in enumerate(B) if A[i] != b])
 
        return new_A, new_B
 
    def find_cycles(self, A: str, B: str) -> List[int]:
        vertices = set(A)
        edges = {v: list() for v in vertices}
 
        for i in range(len(A)):
            edges[A[i]].append((i, B[i]))
 
        cycles = []
 
        visited = {v: False for v in vertices}
 
        def _dfs(start_vertex: str, vertex: str, path: List[int]) -> None:
            if (visited[vertex]):  
                if (vertex == start_vertex):
                    cycles.append(path)
 
                return
 
            visited[vertex] = True
 
            for iv in edges[vertex]:
                _dfs(start_vertex, iv[1], path + [iv[0]])
 
            visited[vertex] = False
 
        for v in vertices:
            _dfs(v, v, [])
 
        return cycles
 
    def swap_for_cycle(self, A: str, cycle: List[int]) -> None:
        target_letters= []
 
        for i in range(len(cycle)):
            if i < len(cycle) - 1:
                target_letters.append(cycle[i + 1])
            else:
                target_letters.append(cycle[0])
 
        new_A = A
 
        for i, letter_index in enumerate(cycle):
            letter = A[letter_index]
            new_A = new_A[:letter_index] + A[target_letters[i]] + new_A[letter_index + 1:]
 
        return new_A

Ресерч

Там же нет вероятностных алгоритмов, интересно. +4 бала за ресерч.  

Конкретно, иногда на

"abcdefabcdefabcdef"
"edcfbebceafcfdabad"

приезжает в ответ 11 вместо 10. Баг ли это движка LeetCode или где-то незаметная рандомизация? Все еще интересно.

Да, Стас, похоже, дело в движке. Рандомизация может возникать из-за того, что при нахождении циклов из символов строк буквы строки А перебираются как элементы множества:

vertices = set(A)
 
<...>
 
for v in vertices:
    <...>

Запустил у себя на машине 1000 раз поиск решения для тех двух строк выше, на которых в LeetCode иногда падает, и все 1000 раз решение оказывалось верным (k = 10). Если же сделать порядок перебора символов однозначным

for v in sorted(vertices):
    <...>
то ни разу из 1000 запусков не удаётся получить ответ 10 — всегда 11.

В общем, выходит, это не баг, а особенность Питона, который там в LeetCode — или, наоборот, того, который у меня :). Элементы ведь во множестве не упорядочены, поэтому в принципе может получаться от раза к разу по-разному. Хм. Да, странно. Элементы могут по-разному упорядочиваться в зависимости от Питона, но на одной и той же машине порядок должен получаться всегда одинаковый. А на LeetCode когда как. Или тогда дело в системе запуска тестов: у них, наверно, много машин, где всё запускается, и тест прогоняется на той, что ему достанется. Получается, случайность может быть не только в коде :)