Постановка задачи 1071. Наибольший общий делитель строк

Для двух строк s и t мы говорим «t делит s» тогда и только тогда, когда s = t t t ... t t (т. е. t объединяется само с собой один или несколько раз).

Дано две строки str1 и str2, вернуть наибольшую строку x, такую, что x делит обе строки: str1 и str2.

Мой мыслительный процесс

Несмотря на то, что в лит-коде эта проблема отмечена как «Легкая», я должен признать, что мне было трудно сразу найти решение.

Позвольте мне просмотреть тестовые примеры, предоставленные leetcode, и просмотреть их, чтобы объяснить мое замешательство.

Тестовые примеры

Ввод: str1 = "ABCABC", str2 = "ABC"
Вывод: «ABC»

Ввод: str1 = "ABABAB", str2 = "ABAB"
Вывод: "AB"

Из постановки задачи и тестового примера 1 я определил, что нам нужно вывести наибольшую строку («ABC»), объединив которую, мы можем получить обе строки. (строка по умолчанию «ABC» === str2 и «ABC» «ABC» === str1).

Однако, посмотрев на тестовый пример 2, я быстро понял, что мое понимание было неправильным, поскольку согласно этому я должен вывести «ABAB», поскольку это самая длинная строка, с помощью которой я могу создать обе строки. Но я приступил к написанию кода и начал намечать решение. (Ошибка новичка?)

Что не удалось/успешно

Мне удалось наметить решение только там, где:

1. найдите НОД двух строк.
2. перейти от длины наименьшей строки к НОД
3. берёт подстроку от наименьшей строки до текущего значения итерации.
4. если обе строки содержат эту подстроку, вернуть эту подстроку в качестве ответа.
5. если строка не найдена, верните "".

Как видите, мое решение не удалось для строк, где str1 содержит str2, но также содержит некоторые другие дополнительные символы. нарушая требование, что s = t t ... t t.

Мне пришлось обратиться за помощью к решению Netcode. Я быстро понял свои проблемы:

1. Я находил НОД длины строки, а НЕ саму строку. Мне нужно найти строку, в которой, повторяя эти строки, я могу создать обе строки без оставшихся символов.

2. Я понял, почему «ABAB» не может быть ответом для тестового примера 2:

• нам нужно найти x такой, чтобы он делил обе строки поровну. поэтому, взяв в качестве строки «ABAB», вы можете полностью создать str2, но для str1 вы получите «ABABABAB». В итоге у вас есть 2 лишних «AB» и вы не можете сказать, что вы полностью создали str1 путем объединения x.

• Длина «ABAB» 4 и длина «ABABAB» 6. НОД двух строк = 2. Следовательно, выходные данные должны быть строкой длины 2.

Выход

Сложность времени и пространства

Временная сложность: В худшем случае мы перебираем Min(str1,str2) и нам нужно воссоздать str1 и str2 так, чтобы это было (str1.length str2.length), поэтому общая временная сложность будет O(min(str1,str2) * (str1.length str2.length))

Пространственная сложность: O(1), поскольку нам не нужно дополнительное пространство.