Leetcode 686 Повторяющееся совпадение строк Не удается понять объяснение - PullRequest
Новая
       45

Leetcode 686 Повторяющееся совпадение строк Не удается понять объяснение

0 голосов
/ 29 июня 2019

У меня возникают проблемы с пониманием того, почему решение совпадения повторяющихся строк в Leetcode доходит до q + 1 повторов A (если A.length () Я читаю другие решения StackOverflow, а также страницы обсуждения Leetcode, но все еще не могу полностью понять решение.

Алгоритм объясняется так: 

Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we 
only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:] 
starts with B, as S is long enough to contain B, and S has period 
at most len(A).

Now, suppose q is the least number for which len(B) <= len(A * q). 
We only need to check whether B is a substring of A * q or A * 
(q+1). If we try k < q, then B has larger length than A * q and 
therefore can't be a substring. When k = q+1, A * k is already big 
enough to try all positions for B; namely, A[i:i+len(B)] == B for i 
= 0, 1, ..., len(A) - 1.

Реализация выглядит следующим образом: 

class Solution {
  public int repeatedStringMatch(String A, String B) {
      int q = 1;
      StringBuilder S = new StringBuilder(A);
      for (; S.length() < B.length(); q++) S.append(A);
      if (S.indexOf(B) >= 0) return q;
      if (S.append(A).indexOf(B) >= 0) return q+1;
      return -1;
  }
}

Я понимаю, что когда A.length () Моя интуиция заключается в том, что после того, как A повторяется некоторое количество раз, устанавливается шаблон, и если B не попадает в этот шаблон / последовательность символов, то независимо от того, сколько раз вы повторяете A, B не будет подстрока повторного А.

Тем не менее, я просто не знаю, почему именно число копий должно соответствовать длине B или добавляется еще 1 копия после A.length () = B.length ().

Если бы кто-то мог прояснить мне эту путаницу, это было бы очень ценно. Спасибо.

1 Ответ

0 голосов
/ 30 июня 2019

Я думаю, вы понимаете большинство из них, так что давайте перейдем к другому базовому примеру. 

ampleex
itsalreadyhereexample
exam

Допустим, B - example, а A - одно из перечисленных.

Для первого случая A.length () == B.length ()
мы проверяем, является ли это подстрокой, и получаем нет как ответ.
Поэтому мы добавляем его еще раз и получаем «ampleexampleex»
и теперь мы получаем результат, в котором A содержит B.

Для второго случая A.length ()> B.length ()
мы проверяем, является ли она подстрокой, и получаем результат, в котором A содержит B.

(Если его здесь не будет, нам все еще нужно проверить, не повторяется ли его,
что эквивалентно первому случаю)

Для третьего случая A.length () поэтому мы повторяем это, пока не охватим длину B
и получите examexam.

Мы видим, что его там нет, поэтому добавим еще раз,
и его до сих пор нет (examexamexam).

Причина, по которой мы должны это сделать, заключается в том, что это может быть более особый случай.
B может быть что-то вроде xamexame - в основном, повторение одного из вариантов As.

(Возможные варианты в этом случае будут повторениями xame, amex, mexa.)

В этом случае он должен быть в повторной форме, которая длиннее, чем B, отсюда и q + 1.

Давайте посмотрим на повторения более подробно:
Длина B может быть не более (A.length () * q) + x, где x равно [0, A.length]. 

A = exam
B = xame[xame]

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

examexam
 xame
 xamex
 xamexa
 xamexam

examexamexam
 xamexame

Добавление еще одного exam к S, ничего не изменит, так как мы уже рассмотрели все возможности (с этого момента новый шаблон не появится).

Если его там нет, это не может быть повторением. Другие сценарии - где это может быть подстрока - были охвачены первым и вторым случаем.

Надеюсь, этот пример поможет вам избавиться от путаницы. Если нет, просто спросите, что вы не понимаете.

...