5. 최장 메모 문자열
8776 단어 데이터 구조와 알고리즘
class Solution {
public String longestPalindrome(String s) {
int len=s.length();
if(len<1){
return "";
}
int res=1,start=0;
int[][] dp=new int[len][len];
for(int i=0;i<len;i++){
dp[i][i]=1;
if(i<len-1){
if(s.charAt(i)==s.charAt(i+1)){
dp[i][i+1]=1;
start=i;
res=2;
}
else{
dp[i][i+1]=0;
}
}
}
for(int i=2;i<len;i++){
for(int j=0;j+i<len;j++){
if(s.charAt(j)==s.charAt(i+j)&&dp[j+1][i+j-1]==1){
dp[j][i+j]=1;
start=j;
res=i+1;
}else{
dp[j][i+j]=0;
}
}
}
return s.substring(start,start+res);
}
}
이 문제는 동적 기획 사상을 사용한다. dp[i+1][j-1]=1&s[i]==s[j]이면 dp[i][j]=1로 s(i, j)를 회문열로 표시한다.위의 for 순환에서 dp 그룹을 초기화하여 문자열 s가 두 문자마다 회문열인지 판단합니다.다음 두 개의 for 순환은 문자열 S의 각 k개의 문자가 회문열(k=3,4,5,...S.length)인지 판단하고 가장 큰 회문열의 길이와 이 길이의 모든 회문열 중 S의 끝에 가장 가까운 회문열의 시작 인덱스를 기록한다.마지막으로 이 메모를 되돌려줍니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
