程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 5 Longest Palindromic Substring(最長子序列),

LeetCode 5 Longest Palindromic Substring(最長子序列),

編輯:C++入門知識

LeetCode 5 Longest Palindromic Substring(最長子序列),


題目來源:https://leetcode.com/problems/longest-palindromic-substring/

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

動態規劃,類似於lcs的解法,數組flag[i][j]記錄s從i到j是不是回文

首先初始化,i>=j時,flag[i][j]=true,這是因為s[i][i]是單字符的回文,當i>j時,為true,是因為有可能出現flag[2][1]這種情況,比如bcaa,當計算s從2到3的時候,s[2]==s[3],這時就要計算s[2+1] ?= s[3-1],總的來說,當i>j時置為true,就是為了考慮j=i+1這種情況。

接著比較s[i] ?= s[j],如果成立,那麼flag[i][j] = flag[i+1][j-1],否則直接flag[i][j]=false

c++代碼:

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int len = s.length(), max = 1, ss = 0, tt = 0;
 5         bool flag[len][len];
 6         for (int i = 0; i < len; i++)
 7             for (int j = 0; j < len; j++)
 8                 if (i >= j)
 9                     flag[i][j] = true;
10                 else flag[i][j] = false;
11         for (int j = 1; j < len; j++)
12             for (int i = 0; i < j; i++)
13             {
14                 if (s[i] == s[j])
15                 {
16                     flag[i][j] = flag[i+1][j-1];
17                     if (flag[i][j] == true && j - i + 1 > max)
18                     {
19                         max = j - i + 1;
20                         ss = i;
21                         tt = j;
22                     }
23                 }
24                 else flag[i][j] = false;
25             }
26         return s.substr(ss, max);
27     }
28 };

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved