동적 프로그래밍을 사용하여 문자열을 단어로 분할

Question

이 문제에서는 문자열을 의미있는 단어로 분할해야합니다. 단어가 존재하는지 여부를 확인하는 사전이 제공됩니다.

나는 " How to split a string into words. Ex: "stringintowords" -> "String Into Words"?에서 여기에 몇 가지 다른 방법을 본 적이

.

나는 다른 방법을 생각하고 일을하거나하지 않을 경우 궁금 해서요.

예 -를

itlookslikeasentence 알고리즘

문자열의 각 문자는 DAG의 노드에 해당합니다.

부울 배열 초기화 t 거짓.

각 노드마다 선택 사항이 있습니다. 이전 하위 배열에 현재 문자를 추가 한 후에도 유효한 단어가 생성되면 추가하고, 그렇지 않으면 추가하지 않고 해당 문자에서 새 단어를 시작하고 bool [ previous_node] = 단어가 거기에서 끝났음을 나타내는 참. 위의 예제에서 bool [1]은 true로 설정됩니다.

이것은 최대 서브 어레이 합계 문제와 유사합니다.

이 알고리즘이 작동합니까?

Answer 1

아니요, 그렇지 않습니다. 당신의 해결책은 모든 단계에서 가능한 한 가장 긴 단어를 취하는데, 항상 효과가있는 것은 아닙니다.

가의 지정된 문자열이 aturtle이라고 가정 해 봅시다 : 여기

는 반증이다. 알고리즘은 a입니다. 그런 다음 이 유효한 단어이므로 t이됩니다. atu은 단어가 아니므로 입력을 분할합니다 (at + urtle). 그러나 urtle을 일련의 유효한 영어 단어로 나눌 방법이 없습니다. 정답은 a + turtle입니다.

올바른 해결 방법 중 하나는 동적 프로그래밍을 사용하는 것입니다. 입력의 첫 번째 i 문자를 올바른 단어 시퀀스로 분할 할 수 있다면 f(i) = true과 같은 함수 f을 정의 할 수 있습니다. 처음에는 f(0) = true이고 나머지 값은 false입니다. l 및 r에 대해 s[l + 1, r]이 유효한 단어 인 경우 f(l)에서 f(r)으로 전환됩니다.

P. 욕심 많은 알고리즘의 다른 유형도 여기에서 작동하지 않습니다. 예를 들어, 가장 긴 단어 대신에 가장 짧은 단어를 사용하면, 예를 들어 입력 atnight에서 작동하지 않습니다. a을 제거한 후에 tnight을 분할 할 방법이 없지만 at + night이 유효합니다. 대답.