美團(tuán)/力扣(647)–回文字串

文章目錄

• 美團(tuán)/力扣(647)--回文字串
• • 一、題目描述
  • 二、分析
  • • 方法一：中心擴(kuò)散
    • 代碼一：
    • 方法二：DP
    • 代碼二：

一、題目描述

力扣：

美團(tuán)：

兄弟們！刷題的重要性！！！

二、分析

方法一：中心擴(kuò)散

• 從開始每個字符進(jìn)行判斷，回文串字符個數(shù)可能為奇數(shù)或偶數(shù)
• 如果是奇數(shù)，則中心字符為當(dāng)前字符，然后向兩邊擴(kuò)散
• 如果是偶數(shù)，則中心字符為當(dāng)前字符和下一個字符，然后向兩邊擴(kuò)散

代碼一：

class Solution { public:int countSubstrings(string s) {if (s.empty()) return 0;int size = s.size();//保存結(jié)果int res = 0;//遍歷每個位置for (int i = 0; i < size; ++i) {helper(s, i, i, res);helper(s, i, i + 1, res);}return res;}//i和j代表向左和向右判斷的指針//如果是奇數(shù)，那么就是自己和自己進(jìn)行比較，那么剛好滿足題意，單個字符就是回文串//如果是偶數(shù)，就是兩個不同的字符進(jìn)行比較void helper(string &s, int i, int j, int &res) {while (i >= 0 && j < s.size() && s[i] == s[j]) {--i;++j;++res;}}};

方法二：DP

• dp[i][j]表示[i, j]范圍內(nèi)字符是否為回文串，i從后向前遍歷，j從i位置向后遍歷，如果s[i] == s[j]，那么i和j滿足下面兩個條件之一，則dp[i][j] = true。
• 如果i和j相鄰或只隔著一個字符，則dp[i][j] = true
• 否則如果dp[i + 1][j - 1] = true，則dp[i][j] = true

代碼二：

class Solution { public:int countSubstrings(string s) {if (s.empty()) return 0;int size = s.size();//保存結(jié)果int res = 0;vector<vector<bool>> dp(size, vector<bool>(size));for (int i = size - 1; i >= 0; --i) {for (int j = i; j < size; ++j) {dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);if (dp[i][j]) ++res; } }return res;} };

總結(jié)

以上是生活随笔為你收集整理的美团/力扣(647)--回文字串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。