※ 引述《ZooseWu (動物園 公告)》之銘言：
: 1930. Unique Length-3 Palindromic Subsequences
: 給你一個字串
: 字串的子序列可以組成一個三個字元的回文字串
: 回傳子字串所有可能的數量
: * 子序列 = 移除某些元素但是不改變順序
: Input: s = "aabca" Output: 3
: - "aba" ("aabca")
: - "aaa" ("aabca")
: - "aca" ("aabca")
: Input: s = "adc" Output: 0
: Input: s = "bbcbaba" Output: 4
: - "bbb" ("bbcbaba")
: - "bcb" ("bbcbaba")
: - "bab" ("bbcbaba")
: - "aba" ("bbcbaba")
思路：
1.要組成一個長度為3的迴文，中間隨便左右兩邊存在一個相同字元即可，所以我們需要在
任意點 i 都可以知道小於 i 和大於 i 的位置分別有幾個字母檢查左右是否都大於0。
2.先遍歷一次字串可以得到所有的字母數量，存到 right[26] 表示右半部份的字母數量。
3.再遍歷一次字串把這個過程的字母數量存到 left[26] 表示 i 左邊的字母數量，如果
left 和 right 的特定字母數量都大於 1 就讓 res + 1。(遍歷過程要更新right[])
4.因為題目要不重複的回文所以我們利用一個二維陣列 used[i][j] 來記錄是否加入過
中間為 i 且左右為 j 的迴文字串，如果加入過就跳過。
Java Code：
---------------------------------------------
class Solution {
public int countPalindromicSubsequence(String s) {
int[] right = new int[26];
int[] left = new int[26];
int res = 0;
for (int i = 0; i < s.length(); i++) {
right[s.charAt(i) - 'a']++;
}
boolean[][] used = new boolean[26][26];
for (int i = 0; i < s.length(); i++) {
int chIdx = s.charAt(i) - 'a';
right[chIdx]--;
for (int j = 0; j < 26; j++) {
if (right[j] > 0 && left[j] > 0) {
if (used[chIdx][j]) continue;
res++;
used[chIdx][j] = true;
}
}
left[chIdx]++;
}
return res;
}
}
---------------------------------------------
我已經不知道我在寫什麼了 姆咪 睡覺==
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699987666.A.56F.html
※ 編輯: Rushia (122.100.73.13 臺灣), 11/15/2023 02:49:36