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);
        }
    }
    
    

    좋은 웹페이지 즐겨찾기