<style>.cnblogs_code { width: auto; border-radius: 4px; box-shadow: 3px 2px 7px rgba(189, 183, 183, 1) } .ws-title { background-color: rgba(40, 120, 156, 1); font-size: 25px; font-family: "微軟雅黑"; padding: 8px 24px; border-radius: 4px; text-align: left; box-shadow: 1px 4px 5px 1px rgba(136, 136, 136, 1); color: rgba(255, 255, 255, 1) } .ws-content { margin-left: 20px; margin-top: 12px }</style>
題目
給定一個字串 s，找到 s 中最長的回文子串，你可以假設 s 的最大長度為 1000，示例
示例一
輸入: "babad"輸出: "bab"
注意: "aba" 也是一個有效答案 示例二 輸入: "cbbd"
輸出: "bb"
解題
回文：字串正向讀和反向讀是一樣就叫回文
- 一個字符: 肯定是回文
- 兩個字符：相等
- 三個字符: 首尾字符相等
- 四個字符: 若首尾相等 && 中間是回文
- .......
- Str[i,j] = str[i] == str[j] && str[i+1,j-1] == 回文
根據上面規律，想到用動態規劃解決這個問題
public string LongestPalindrome(string s) { if (string.IsNullOrEmpty(s) || s.Length <= 1) return s; var result = string.Empty; var dp = new bool[s.Length, s.Length]; for (int i = s.Length - 1; i >= 0; i--) { for (int k = i; k < s.Length; k++) { dp[i, k] = s[i] == s[k] && (k - i < 2 || dp[i + 1, k - 1]); if (dp[i, k] && (k - i + 1) > result.Length) { result = s.Substring(i, k - i + 1); } } } return result; }View Code
相關知識
- 動態規劃
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring/submissions
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137716.html
標籤：其他
上一篇：資料結構之——八大排序演算法