Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Ссылка на сайт
Substring with Concatenation of All Words
трудность
Hard
описывать
Для заданной строки s в качестве материнской строки и ряда строковых слов одинаковой длины требуется вернуть все позиции в s, чтобы все слова можно было найти с этой позиции, и все слова встречались только один раз.
You are given a string, s , and a list of words, words , that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Пример 1:
**Input:
s =** "barfoothefoobarman",
**words =** ["foo","bar"]
Output: [0,9]
## Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Пример 2:
**Input:
s =** "wordgoodgoodgoodbestword",
**words =** ["word","good","best","word"]
Output: []
отвечать
Сложность этого вопроса Трудно. Честно говоря, это непросто, особенно если его задают в интервью, боюсь, лучший ответ придумать сложно.
Насилие
Это все еще старое правило: мы соглашаемся на следующий лучший вариант, забываем лучший ответ, сначала придумываем простой метод, а затем думаем, как его оптимизировать. Самый простой способ это конечно брутфорс, мы сначала проходим все начальные позиции, а уже потом сопоставляем слово за словом. Ответ записывается при успешном совпадении, а при неудаче поиск продолжается до следующей позиции.
Это выглядит хорошо, но есть некоторые детали, о которых следует знать. Например, в заголовке сказано только, что длина слов одинакова, и не сказано, будут ли слова повторяться. Очевидно, мы должны учитывать повторение слов, поскольку нам нужно учитывать повторение слов, мы не можем использовать набор для записи того, появилось ли слово, но нам нужно подсчитать количество вхождений каждого слова. Во-вторых, при обходе нам также нужно подсчитать количество совпавших в данный момент слов.
Идея насилия в этом вопросе относительно ясна, а код написать несложно:
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
n = len(s)
# 单词不存在直接返回
if len(words) == 0:
return []
ret = []
word_cnt = len(words)
m = len(words[0])
words_dict = {}
# 初始化，记录词表
for word in words:
words_dict[word] = words_dict.get(word, 0) + 1
# 枚举开始的位置
for i in range(n):
cur_dict = {}
matched = 0
# 每次遍历一个单词
for start in range(i, n, m):
w = s[start: start+m]
# 如果单词存在，并且当前匹配的数量小于目标，则进行记录
if w in words_dict and cur_dict.get(w, 0) < words_dict[w]:
cur_dict[w] = cur_dict.get(w, 0) + 1
matched += 1
else:
break
# 所有单词已经匹配
if matched == word_cnt:
ret.append(i)
break
return ret
Давайте проанализируем сложность этого алгоритма, мы используем два слоя циклов при поиске. Внешний цикл проходит все длины, а внутренний цикл перебирается пословно. В крайних случаях можно пройти всю строку. Сложность
. Но так как m постоянно и в крайних случаях равно 1, наихудшая временная сложность всего алгоритма по-прежнему
.
Официальная карта этого вопроса не строгая, можно пройти даже насильственным методом. Если это формальное соревнование алгоритмов, то время застопорится, и насильственный метод точно не пройдет. Значит, надо оптимизировать.
Two pointers
Прежде чем объяснять схему оптимизации, давайте проведем тщательный анализ. В этом вопросе, поскольку нам нужно найти все ответы, удовлетворяющие условиям, очевидно, нам нужно пройти через все возможные ситуации. То есть обход неизбежен, в этом вопросе мы точно не можем сами сгенерировать ответ, и мы должны пройти. Грубо говоря, идея обойти все ситуации правильная, нам нужно не найти новый метод, а оптимизировать его.
Как только вы поймете, как двигаться вперед, вы можете перейти ко второму вопросу. Где проблема в методе перебора, который приводит к большим временным затратам, и где его можно оптимизировать?
Понять ход мыслей несложно, есть всего две ситуации, в которых будет повторение. Давайте перечислим их ниже.Для удобства просмотра и понимания я использую [] для обозначения слова, а разные числа в [] представляют разные слова.
- ...[1][2][3]....[1][2][3].... Это самый простой случай. Существует еще один правильный ответ на некотором расстоянии от одного правильного ответа, и, поскольку мы выходим каждый раз, когда находим правильный ответ, нам нужно пройти много раз, чтобы найти следующий ответ.
- ....[1][2][1][2][3]...., в этом случае, после того, как мы нашли первое неправильное [1][2], мы обнаружили, что оно было неверным, поэтому выходим петля. Затем нам нужно пройти 2m раз (длина слова равна m), прежде чем мы сможем найти ответ [1][2][3]. Если бы мы могли просто допустить ошибку и продолжить поиск, мы могли бы сразу найти ответ.
Совмещая два вышеуказанных пункта, схема оптимизации на самом деле очень понятна. То есть, нашли мы ответ или нет, мы не должны бросать работу, когда сталкиваемся с проблемой, мы должны продолжать искать другие возможные ответы.
Оптимизация 1
Итак, мы получаем первую оптимизацию, так как мы будем завершать обход каждый раз, независимо от того, успешен он или нет, и каждый раз, когда мы обходимся, мы будем получать строку длины m и сравнивать ее с тезаурусом. Затем, когда мы пересекаем начальную позицию, нам не нужно проходить длину n, а нужно только проходить длину m.
Например, если s='abcgoodgoodgirl', тезаурус будет ['good', 'girl'].
При первом обходе a мы можем получить следующие слова: abcg, oodg, oodg, irl.
Второй обход обход b, получаются слова: a, bcgo, odgo, odgi, rl
Третий обход c, слова: ab, cgoo, dgoo, dgir, l
Наконец, траверс g, слова: abc, хорошо, хорошо, девочка.
Таким образом, нам нужно пройти всего 4 раза, чтобы получить все комбинации слов. То есть мы сначала получаем все словосочетания, а потом находим ответ из этих сочетаний. Таким образом, мы уменьшили количество петель для самого внешнего слоя с n до m.
Оптимизация 2
Все еще ссылаясь на приведенный выше пример, мы можем обнаружить, что в приведенных выше 4 обходах только последний может найти ответ. Посмотрим на содержание этого обхода отдельно: abc, good, good, girl. Так как тезаурус ['хорошая', 'девушка'], когда мы проходим это словосочетание, мы столкнемся с двумя хорошими, что несовместимо с нашим просроченным. Согласно нормальному мышлению, мы должны пропустить, затем очистить записанный ответ и начать обход со следующего слова.
Это, конечно, возможно, но на самом деле есть лучшие решения этой проблемы. Если вы знакомы с алгоритмом двух указателей, вы обнаружите, что это классический сценарий применения алгоритма двух указателей. То, что мы ищем, — это интервал, состоящий из нескольких последовательных слов, тогда мы можем поддерживать этот интервал с двумя указателями. Что делать, если мы читаем лишнее слово справа, а число выходит за границы? Очень просто, мы можем перемещать левую границу и выдвигать несколько слов, пока их не будет достаточно.
Если вы не знаете алгоритм двух указателей, вы можете щелкнуть ссылку ниже, чтобы просмотреть предыдущий контент:
Yiwen изучает алгоритм двух указателей
Разобравшись с вышеуказанными идеями, мы можем написать код:
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
n = len(s)
if len(words) == 0:
return []
# 初始化的部分和之前一样
ret = []
word_cnt = len(words)
m = len(words[0])
words_dict = {}
for word in words:
words_dict[word] = words_dict.get(word, 0) + 1
# 只遍历[0, m)
for i in range(m):
cur_dict = {}
# l和r表示当前的区间两侧端点
l = i
matched = 0
for r in range(i, n, m):
# 获取当前的单词
word = s[r: r+m]
# 如果单词不在词库当中，清空之前的数据
if word not in words_dict:
# l赋值成下一个开始的r
l = r + m
# 所有匹配记录清空
matched = 0
cur_dict = {}
continue
# 记录单词
cur_dict[word] = cur_dict.get(word, 0) + 1
matched += 1
# 如果数量超界的话，就弹出左侧
while cur_dict[word] > words_dict[word]:
w = s[l: l+m]
cur_dict[w] -= 1
matched -= 1
l += m
# 如果匹配数量一致，则记录答案，也就是l的位置
if matched == word_cnt:
ret.append(l)
return ret
Код не длинный, но деталей в нем все равно много, что касается обработки границ и логики некоторых операций, то написать правильно за один раз все равно очень сложно. Заинтересованные студенты могут попробовать его и посмотреть, смогут ли они написать его за один раз, не обращаясь к моему коду.
Этот вопрос вызывает у меня самое сильное ощущение, что на первый взгляд это проблема сопоставления строк. Это заставит нас задуматься о различных алгоритмах сопоставления строк, но на самом деле это проблема оптимизации обхода. У этого вопроса низкий балл в LeetCode, и многие люди дали ему плохую оценку, возможно, потому, что многие люди были обмануты задавшим вопрос. Но я думаю, что это очень интересно, это очень упражнение, а не какое-то безмозглое мучение. В конце концов, в соревнованиях по алгоритмам вопрошающие часто «обманывают» участников, что является одной из прелестей алгоритмов.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, отсканируйте код и нажмитеобрати внимание наЧто ж, твое маленькое усилие много значит для меня.