動機

的確是dp，但也可以不用dp… 好像只要是回文都可以用列舉中央去解

Problem

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = babadOutput: babNote: aba is also a valid answer.

Example 2:

Input: s = cbbdOutput: bb

Example 3:

Input: s = aOutput: a

Example 4:

Input: s = acOutput: a

 

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Ver1: TLE

定義dp[i][j]為s[i:j]的回文長度，如果不是回文就是0

所以可以列舉所有可能的子字串，去看

但是要怎麼加速?

通常列舉的資料如果是可以遞迴的或是可以一層一層的疊上去就可以考慮用dp 但就算是列舉的資料如果是可以遞迴的或是可以一層一層的疊上去，如果其內容不與其他答案重疊，就會變成Divide and Conquer

@DP = Array.new(1000) {Array.new(1000,nil)}
def f(s,i,j,dp)
    if !dp[i][j]
        if i >= s.size || j < 0 || i > j
            dp[i][j] = -1
        elsif s[i] == s[j] && i+1 < s.size && j-1 >= 0 && i+1 <= j-1
            ret = f(s,i+1,j-1,dp)
            if ret > 0
                dp[i][j] = 2 + ret
            else
                dp[i][j] = 0
            end
        else
            dp[i][j] = 0
        end
    end
    return dp[i][j]
end
def find_out_continuousSeq(s,dp)
    cc = nil
    acc = 0
    old = 0
    s.each_char.with_index do |c,i|
        if c == cc
            acc += 1
            dp[i-acc][i] = dp[i-acc][i-1] + 1
        else
            acc = 0
        end
        cc = c
    end
end
def longest_palindrome(s)
    #dp = Array.new(s.size){Array.new(s.size,nil)}
    dp = @DP
    dp.map! {|x| x.fill(nil)}
    ans = 0
    str = ""
    (0...s.size).each {|x| dp[x][x] = 1}
    find_out_continuousSeq(s,dp)
    (0...s.size).each do |i|
        break if (s.size-i) < ans
        ((i+ans)...s.size).each do |j|
            f(s,i,j,dp)
            old = ans
            ans = [ans,f(s,i,j,dp)].compact.max
            if ans > old
                i, j = [i,j].sort
                str = s[i..j]
                old = ans
            end
        end
    end
    return str
end

寫到後面才想起，Ruby與Python不能操作巨大的array 十分耗時

如果要的話，就用hash table替代

Ver2: AC

// i~j之間的回文長度，不是回文就是0
int dp[1000][1000] = {-2};
class Solution {
public:
    int f(string &s,int i,int j) {
        if(dp[i][j] == -2) {
            if(i >= s.length() || j < 0 || i > j)
                dp[i][j] = -1;
            else if(s[i] == s[j] && i+1 < s.length() && j-1 >= 0 && i+1 <= j-1) {
                int ret = f(s,i+1,j-1);
                dp[i][j] = ret > 0 ? ret+2 : 0;
            }
            else
                dp[i][j] = 0;
        }
        return dp[i][j];
    }
    void initDP() {
        for(int i=0;i<1000;i++)
            for(int j=0;j<1000;j++)
                dp[i][j] = -2;
        for(int i=0;i<1000;i++)
            dp[i][i] = 1;
    }
    void find_out_continuousSeq(string &s) {
        char cc='-';
        int acc = 0;
        for(int i=0;i<s.length();i++) {
            if(s[i] == cc)
                acc++, dp[i-acc][i] = dp[i-acc][i-1] + 1;
            else
                acc = 0;
            cc = s[i];
        }
        
    }
    string longestPalindrome(string s) {
        int a=0,b=0;
        initDP();
        int ans = 0;
        find_out_continuousSeq(s); //先找出連續的string baaab的aaa
        for(int i=0;i<s.length();i++) {
            if(s.length()-i < ans)
               break;
            
            for(int j=i+ans;j<s.length();j++){
                int old = ans;
                ans = max(ans,f(s,i,j));
                if(ans>old)
                    a=i,b=j,old=ans;
            }
                
        }
        //cout << ans <<','<<a <<','<<b<< '\n';
        return s.substr(a,b-a+1);
    }
};

比較短的DP，但在py會TLE

class Solution:
    def longestPalindrome(self, s: str) -> str:
        @cache
        def isPalin(i,j):
            if j-i < 0:
                return False
            elif j-i == 1 or j-i == 0:
                return True
            else:
                return s[i] == s[j-1] and isPalin(i+1,j-1)
        a,b = 0,0
        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                if j-i > b-a and isPalin(i,j):
                    a,b=i,j
        return s[a:b]

列舉中央

列舉中央開始擴展回文也是n平方!! 同時這也是py能被AC的解

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def center(a,b):
            while 0 <= a < len(s) and 0 <= b < len(s) and s[a] == s[b]:
                a,b = a-1,b+1
            return [a+1,b]
        x,y = 0,0
        for i in range(len(s)):
            for (a,b) in [center(i,i), center(i-1,i)]:
                if 0 <= a < len(s) and 0 < b <= len(s) and y-x < b-a:
                    x,y=a,b
        return s[x:y]