5. 문자열 s를 지정하고 s에서 가장 긴 메모 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.(dp)

문자열 s를 지정하고 s에서 가장 긴 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.

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 => do[i][i+len]=1

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에 따라 라이센스가 부여됩니다.

5. 문자열 s를 지정하고 s에서 가장 긴 메모 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.(dp)

문자열 s를 지정하고 s에서 가장 긴 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.

좋은 웹페이지 즐겨찾기