Leetcode — 5. Longest Palindromic Substring (中文)

問題連結: https://leetcode.com/problems/longest-palindromic-substring/

給予一字串 s, 回傳在 s中可找到最長的回文子字串

範例
Input: s = "babad"
Output: "bab" -> 因s字串中, 最長可組成的回文子字串長度是3, 答案回傳"aba"也算對

想法:

先來講回文的定義, 以及我們怎麼判斷一個字串是否為回文

回文就是一個字串我們從頭讀到尾跟從尾巴讀回去的時候, 結果是一樣的(例如 我為人人,人人為我 就是一個回文), 因此我們其實有兩種判別字串是否為回文的方式, 兩種方法皆需要用到兩個pointer i和j, 這樣我們就能同時比對兩個不同位置的字元是否相等

🔧方法1. 我們把pointer i放在字串的第一個字元, pointer j放在字串的最後一個字元, 在比對完i和j指的字元後, pointer i跟pointer j都將會往中間移動, 如果這個字串是回文的話, 那pointer i和pointer j指的字元都會一樣, 直到i和j在字串最中間兩點相遇或交錯

🔧方法2. 這次我們pointer i和pointer j的起始點在字串中間, 分別讓i往字串的第一個字走(也就是往左走到底), 讓j往字串最後一個字走(也就是往右走到底), 如同方法1, pointer i和pointer j在走到底前, 他們兩個指的字元也應該要一模一樣, 整個字串才能被稱為是回文

當然, 你可以檢查這個字串的所有可能子字串, 篩選出長度最長的回文子字串並回傳, 那我們要做的事情就是 - 在指定的各長度之下, 組成這個字串中的所有子字串們, 因為我們將會從最長長度開始組個子字串, 因此若我們一發現現在的子字串是回文, 我們就直接回傳這個答案了

⚠️在我們的helper method中, 我們用方法1或方法2來解都沒有插, 畢竟這兩個方法時間複雜度是一樣的

以下為496ms的程式碼, 贏過10% —

public String longestPalindrome(String s) {
        int n = s.length();
        if(n<=1)
            return s;
        for(int len=n;len>=2;len--)
        {
            for(int left=0;left+len<=n;left++)
            {
                int right = left+len-1;
                if(isPal(s,left,right))
                    return s.substring(left, right+1);
            }
        }
        return s.substring(0,1);
    }
    public boolean isPal(String s, int l,int r){
        while(l<r)
        {
            if(s.charAt(l++)!=s.charAt(r--))
                return false;
        }
        return true;
    }

因為我們會重複的檢查同個範圍內的子字串是否為回文, 因此我們也可以運用動態規劃的邏輯 - 把某範圍的子字串是否為回文這個結果存進二維陣列中, 因此, 我們將會用dp[i][j]來代表從index i到index j 這個範圍中的子字串是否為回文, 舉例來說 dp[0][2]代表的就是子字串"abc"在字串"abcde"中是否為回文

因此, 我們將會利用剛剛提過的方法2來確定我們的子字串是否為回文, 我們這次會從長度小的子字串開始確認其是否為回文, 這樣等等我們才能好好利用找過的子字串,來確認現在的字串是否為回文

比如說, 假設我們已知“acbca”是回文了
那如果我們想知道“xacbcax”是否為回文, 我們只要比對第一個字元跟最後一個字元是否相同, 若相同, 就可以直接判斷“xacbcax”就跟它裡面的子字串“acbca”一樣, 也是回文

代表我們只要檢查最左邊的字元是否跟最右邊的字元相同, 若相同, 則我們就可以靠中間的子字串是否為回文的結果來判斷現在組成的字串是否為回文 (因為長度比較小, 所以代表我們前一輪就已經檢查過那個長度的所有子字串是否為回文了)

以下為193ms的程式碼, 贏過 20% —

public String longestPalindrome(String s) {
        int n = s.length();
        if(n<=1)
            return s;
        String rst = s.substring(0,1);
        boolean[][] dp = new boolean[n][n];
        for(int len=1;len<=n;len++)
        {
            for(int left=0;left+len<=n;left++)
            {
                int right = left+len-1;
                if(s.charAt(left)!=s.charAt(right))
                    continue;
                if(right-left<=2)//like "a" "aa" "aba"
                    dp[left][right] = true;
                else
                    dp[left][right] = dp[left+1][right-1];
                int curLen = rst.length();
                if(dp[left][right] && curLen < len)
                    rst = s.substring(left,right+1);
            }
        }
        return rst;
    }

然而,這樣的時間複雜度仍然很高, 因為我們幾乎是確認完所有這個字串中的所有子字串是否為回文, 才回傳的出答案

程式邏輯:

在這題你並不需要回傳所有最長的子字串們, 代表我們也不需要確定每個子字串是否是回文了, 只要你回傳的回文子字串是整個字串中可找到最長回文子字串的其中一個就可以

這次, 我們不猜最終子字串的起點和終點了, 我們這次改成猜最終子字串的中間點

總共有兩種回文字串 — 奇數長度跟偶數長度的回文, 因此, 回文的中間點可能有一個或兩個

因為每個位置都有可能成為最長回文子字串, 因此我們會用一個迴圈來去試, 我們會有一個helper method, 我們會給予我們指定位置的left pointer和right pointer,重複我們剛剛在這篇文章最一開始講的方法2的動作, 直到left pointer和right pointer指的是不同字元為止

我們會在每個位置(也就是我們每個不同子字串的中間點)呼叫helper method兩次, 因為我們不知這個位置將組成的是奇數長度還是偶數長度的回文字串, 因此我們兩個都傳

舉例來說, 假設字串為"abcde"
那假設我們要找b為中間點的子字串, 那b為中間點所能組成的最長子字串就是"abc"和"abcd"

以下為26ms 的程式碼, 贏過 63% —

public String longestPalindrome(String s) {
        String rst = "";
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            //i is the mid point of the substr
            String cur = helper(s, i-1, i+1);
            if(cur.length()>rst.length())
                rst = cur;
            cur = helper(s, i, i+1);
            if(cur.length()>rst.length())
                rst = cur;
        }
        return rst;
    }
    public String helper(String s, int left,int right){
        int n = s.length();
        while(left>=0 && right<n 
              && s.charAt(left) == s.charAt(right))
        {
            left--;
            right++;
        }
        //here: s[left] != s[right]
        return s.substring(left+1, right);
    }

因為i代表的是我們潛在回文子字串的中間點, 我們在這裡能組成的最長子字串長度就是i到左或i到右的距離的兩倍(看往哪走比較快走到底就是他, 畢竟因為兩邊需要平衡, 離邊界比較遠的一側需要遷就另一側)

比如說在”abcdef”中 i=1 的時候, 我們能組成最長字串就是”abcd”

因此, 若我們發現現在位置i根本不可能組成比現在答案字串還長的子字串的時候, 我們可以直接不去呼叫helper method, 去找下一個

等等, 但若我們發現i已經不可能組成比現在答案字串還長的子字串的時候, 那i之後的也更不可能了, 因為我們一直往右走, 代表我們能組的子字串長度越來越小, 因此, 我們其實可以在我們發現i已不可能再創最佳解的時候, 就果斷回傳現有的答案回去了

以下為 17ms 的程式碼, 贏過 94.6% —

public String longestPalindrome(String s) {
        String rst = "";
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            int longest = Math.min(i, n-i+1);
            if(rst.length() > longest*2)
                return rst;
            //i is the mid point of the substr
            String cur = helper(s, i-1, i+1);
            if(cur.length()>rst.length())
                rst = cur;
            cur = helper(s, i, i+1);
            if(cur.length()>rst.length())
                rst = cur;
        }
        return rst;
    }
    public String helper(String s, int left,int right){
        int n = s.length();
        while(left>=0 && right<n 
              && s.charAt(left) == s.charAt(right))
        {
            left--;
            right++;
        }
        //here: s[left] != s[right]
        return s.substring(left+1, right);
    }