최장 회문열 총결산
(1) Manacher 알고리즘은 O(n)의 복잡도에 도달할 수 있으나 묘사하기 어렵고 고전적이지 않기 때문에 반드시 파악할 필요가 없다.
(2) 동태적으로 기획하는 방법은 곰곰이 생각해 볼 만하다
Define a 2-dimension array "table"and let table[i][j] denote whether substring from i to j is palindrome.(2차원 그룹을 정의합니다.table[i][j]로 i에서 j까지의 하위 문자열이 회문 문자열인지 여부를 나타냅니다)
Start condition:
table[i][i] == 1;
table[i][i+1] == 1 => s.charAt(i) == s.charAt(i+1)
Changing condition: (이것은 일종의 귀속적인 사고방식이다.table[i+1][j-1]는 회문열이고str[i]와str[j]가 같기 때문에 i에서 j까지는 회문열, 즉table[i][j]=1)이다.
table[i][j] == 1 => table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)(3) 참고자료 2의 O(n2) 알고리즘도 뚜렷하다.
안팎으로 판단하다.즉, 하위 문자열 (예: dd) 이 대칭인지 아닌지를 먼저 판단하는 것이다.만약 그것이 (dd) 대칭적이지 않다면, 이 하위 문자열의 양쪽 끝에 각각 한 문자를 연장해서 얻은 문자열은 틀림없이 대칭적이지 않을 것이다.만약 그것(dd)이 대칭적이라면, 그것(dd)의 양쪽 끝에 연장된 문자가 서로 같은지 아닌지를 판단하고, 만약 서로 같다면 연장된 문자열은 대칭적이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
