5. 문자열 s를 지정하고 s에서 가장 긴 메모 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.(dp)
9326 단어 일상적인 문제 풀이
문자열 s를 지정하고 s에서 가장 긴 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.
dp방정식
class Solution {
public String longestPalindrome(String s) {
if(s.equals("")||s.length()==1)
return s;
int [][] dp=new int[s.length()][s.length()];
char []num=s.toCharArray();
int start=0;
int maxLen=1;
for(int i=0;i<s.length();i++)//
{
dp[i][i]=1;
if(i+1<s.length()&&num[i]==num[i+1])
{dp[i][i+1]=1; start=i;maxLen=2; }
}
// , len 2
for(int len=2;len<num.length;len++)
{
for(int i=0;i<num.length;i++)
{
if (i + len < num.length&&num[i] == num[i + len]) {
dp[i][i + len] = dp[i + 1][i + len - 1];// dp[i][i+len]
if (dp[i][i + len] ==1&& len + 1 > maxLen) {//
maxLen = len + 1;
start = i;
}
}
}
}
return new String(num,start,maxLen);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
5. 문자열 s를 지정하고 s에서 가장 긴 메모 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.(dp)dp방정식 dp[i][j]는 i부터 j까지 회문열 을 대표한다 dp[i][i]=1; if(s[i]==s[i+1]) dp[i][i+1]=1; s[i]==s[i+len] && dp[i+1][i+len-1]==1 => d...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.