推 plzza0cats: 大師 我都ptt小天使問程式語言怎麼寫 10/24 11:35
推 pandix: 大師 10/24 14:22
→ NTHUlagka: 大師 10/24 19:52
1239. Maximum Length of a Concatenated String with Unique Characters
給予一個字串陣列arr，判斷裡面的任意字串拼接後的最長字串長度，需滿足：
1.任意字串拼接時不可改變相對於arr的先後順序，例如：arr = {"a", "b"} 的話
不可以這樣拼："ba"，其中不拼接任何字串拿到的字串例如："a" "b" 也是合法的。
2.拼接完的字串必須每個字元都是獨特的：
"a" (O) 長度為1
"aa" (X) 非法，長度為0
Example：
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" +
"ers") and "acters" ("act" + "ers").
思路：
1.我研究了一下應該是只能窮舉，因為要窮舉所以就用回溯法來剪枝。
2.每次都從start加入當前字串到列表並進入下層。
3.當curr的size > 1 時，檢查是否包含重複字元，若包含重複字元直接返回0，後面都
不用找了，否則計算共有幾個字元並令他為max。
4.比較當前max和往更深處找的數字哪個大更新並max，最後返回max。
JavaCode：
class Solution {
public int maxLength(List<String> arr) {
return backTracking(arr, new ArrayList<>(), 0);
}
private int backTracking(List<String> arr, List<String> curr, int start) {
if(start > arr.size()) return 0;
int max = 0;
int[] count = new int[26];
for(String s: curr) {
for(char c : s.toCharArray()){
if(count[c - 'a'] != 0)
return 0;
count[c - 'a']++;
max++;
}
}
for(int i = start; i < arr.size(); i++) {
curr.add(arr.get(i));
max = Math.max(max, backTracking(arr, curr, i + 1));
curr.remove(curr.size() - 1);
}
return max;
}
}
芒果假面
https://i.imgur.com/acHi4CL.png
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.49.151 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666582388.A.7DC.html
※ 編輯: Rushia (1.160.49.151 臺灣), 10/24/2022 11:34:56