O (n^2)에 공백없는 문자열을 재구성하십시오.

Question

알고리즘이 올바른지 확인하고 싶습니다. 생략 모두 공백으로 n 문자의 문자열이 주어

,

Ex: "itwasthebestoftimes" 

문자열을 단어의 시퀀스로 분할 될 수 있는지를 결정하는 동적 프로그래밍 알고리즘을 제공하고있는 유효한 문자열을 재구성 O (n)의 공백.

내 생각 :

먼저 문자열의 모든 문자열을 찾을 수 (O (N ²)), 각 문자열지도 간격으로 공간과 길이에 위치합니다.

Ex: "it was the best" 
     [] [-] [-] [--] 
     [---] []  
      [] 

(보기 쉽도록 공간이 추가됨). 위의 예에서

은 "그것"유효하며 등 문자열 "TWAS"3 가져도 유효 "을"2 간격 값을 취득하고, 제

의 값을 얻는다 그런 다음 간격의 집합에서 최대 비 중첩 길이를 찾기 위해 최소 최대 문제로 축소됩니다. 유효한 문자열은 모든 글자를 포함해야하므로, 최대 길이가 겹치지 않는 간격이 답이 될 것이고, 이것을 찾는 것은 Theta (n * log (n))를 취한다.

따라서 해결책은 O를 취할 것 (N ² + N * 로그 (N)) = O (N ²)

내 올바른 생각인가?

Answer 1

당신의 생각은 괜찮습니다. (중복되지 않는 최대 간격을 찾는 문제에 대한 O (n log n) 해결책을 알고 있다고 가정하고, O (n)에서 단어 간격을 찾는 방법을 알고 있어야합니다.^2) 시간. 그러나 문제는 당신이 생각하는 것보다 쉽습니다.

W[0...n]을 만듭니다. W[i]은 i부터 그 문자열을 단어로자를 방법이 없다면 0이 될 것이고, 그렇지 않으면 문자열을 유효하게 자르기 시작하는 단어의 길이를 저장할 것입니다. 그런 다음

: 당신이 트라이에 사전을 유지하는 경우

W[i] = min(j such that W[i:j] is a word, and i+j = n or W[i+j]>0) 
     or 0 if there's no such j. 

, 당신은 계산할 수 W[i] O에서 (N-) 시간은 이미 W[n-1]에 W[i+1]을 계산 한 가정하면. 즉 O (n^2) 시간 안에 W을 모두 계산할 수 있습니다. 또는 사전에있는 단어의 최대 길이가 k 인 경우 O (nk)시에 입력 할 수 있습니다.

당신이 W을 모두 계산하면 및 경우에만 W[0]는 어떻게되는 줄로 이동하는 문자열 선택합니까 0