720 - C++ LeetCode

【Leetcode】C++ - [5] Longest Palindromic Substring 個人筆記 | 內含 C++ string.substr() 用法筆記

題目出處

https://leetcode.com/problems/longest-palindromic-substring/

難度

Medium

個人範例程式碼 – 2022/8/12 一刷

class Solution {
public:
    string longestPalindrome(string s) {
        string tmp_ans, final_ans = "";
        for(int i = 0; i < s.length() ; i++){
            tmp_ans = is_palindrome(s, i, i);
            if(tmp_ans.length() > final_ans.length())
                final_ans = tmp_ans;

            tmp_ans = is_palindrome(s, i, i+1);
            if(tmp_ans.length() > final_ans.length())
                final_ans = tmp_ans;
        }

        return final_ans;
    }

    string is_palindrome(string s, int start, int end){
        while(0 <= start && end < s.length() && s[start] == s[end]){
            start -= 1;
            end += 1;
        }

        // s.substr(start, len)
        // s[start+1:end] -> s.substr(start+1, end-(start+1))
        string split_string = s.substr(start+1, end-(start+1));
        // cout << split_string << endl;
        return split_string;   
    }
};


/* python solution
class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        for i in range(len(s)):
            tmp_ans = self.is_palindrome(s, i, i)
            if len(tmp_ans) > len(ans):
                ans = tmp_ans

            tmp_ans = self.is_palindrome(s, i, i+1)
            if len(tmp_ans) > len(ans):
                ans = tmp_ans

        return ans

    def is_palindrome(self, s, start, end):
        while(0 <= start and end < len(s) and s[start] == s[end]):
            start -= 1
            end += 1

        # print(s[start+1:end])
        return s[start+1:end]
*/

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

  • 個人是從 python 練熟後，把概念帶過來練習 C++，「python 解」可參考：

https://wongwongnotes-github-io.pages.dev/python/python_leetcode/python-leetcode-5/

算法說明

以中間作為 palidrome 搜尋開始的起始位置，
另外寫一個驗證 palindrome 用的 function。

corner case 特殊情況處理

一起在判斷 palindrome 的 function 中做掉。

Boundary conditions/ Edge conditions 邊際情況處理

  • 注意搜尋範圍 0 <= start, end < len(s)
  • 注意離開迴圈後，回傳 s[start+1:end]，而不是直覺的 s[start:end+1]

C++ substr 用法複習

在 python 裡面，我們可以比較輕鬆的使用 string split，
我們在 C++ 需要使用 string.substr() 來代替，
用法是 「string.substr(start, len)」，

可以養成參考官方文件的習慣：

Reference