文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 回溯超時解
    • 2.2 回溯優化
    • 2.3 動態規劃

1. 題目

給定一個字符串數組 arr，字符串 s 是將 arr 某一子序列字符串連接所得的字符串，如果 s 中的每一個字符都只出現過一次，那么它就是一個可行解。

請返回所有可行解 s 中最長長度。

示例 1： 輸入：arr = ["un","iq","ue"] 輸出：4 解釋：所有可能的串聯組合是 "","un","iq","ue","uniq" 和 "ique"，最大長度為 4。示例 2： 輸入：arr = ["cha","r","act","ers"] 輸出：6 解釋：可能的解答有 "chaers" 和 "acters"。示例 3： 輸入：arr = ["abcdefghijklmnopqrstuvwxyz"] 輸出：26提示： 1 <= arr.length <= 16 1 <= arr[i].length <= 26 arr[i] 中只含有小寫英文字母

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 回溯超時解

class Solution {int maxlen = 0; public:int maxLength(vector<string>& arr) {int count = 0;dfs(arr, count, 0, 0);return maxlen;}void dfs(vector<string>& arr, int count, int idx, int len){bool ok;for(int i = idx, j; i < arr.size(); ++i){ //不應該加這層循環，超時了！！！ok = true;for(j = 0; j < arr[i].size(); ++j){if((count>>(arr[i][j]-'a'))&1)//已經存在該字符{ok = false;break;}}if(ok){for(j = 0; j < arr[i].size(); ++j){count |= (1<<(arr[i][j]-'a'));}len += arr[i].size();maxlen = max(maxlen, len);dfs(arr, count, idx+1, len);len -= arr[i].size();for(j = 0; j < arr[i].size(); ++j){count &= ~(1<<(arr[i][j]-'a'));}}}} };

2.2 回溯優化

• 把每個字符的狀態存在 int 的二進制位上
• 每個單詞兩種選擇，選或者不選

class Solution {int maxlen = 0; public:int maxLength(vector<string>& arr) {dfs(arr, 0, 0, 0);return maxlen;}void dfs(vector<string>& arr, int count, int i, int len){maxlen = max(maxlen, len);if(i == arr.size())return;int j, origin = count;for(j = 0; j < arr[i].size(); ++j){if((count>>(arr[i][j]-'a'))&1)//已經存在該字符{return dfs(arr, origin, i+1, len);//這個單詞不選}count |= (1<<(arr[i][j]-'a'));}dfs(arr, origin, i+1, len);//該單詞不選 dfs(arr, count, i+1, len+arr[i].size()); //該單詞選} };

8 ms 8.2 MB

2.3 動態規劃

class Solution { public:int maxLength(vector<string>& arr) {int i, j, n = arr.size(), maxlen = 0, state, nextstate;bool ok;map<int,int> dp;//字符數狀態int表示，最大長度dp[0] = 0;for(i = 0; i < n; ++i){for(auto it = dp.rbegin(); it != dp.rend(); ++it){ //逆序遍歷，新生成的狀態加在末尾了不會干擾本次//本題正序，也可以，因為同一個單詞加2次肯定重復，//不會新生成下一個state，但是無畏的遍歷多了，耗時788 ms 13.8 MBstate = it->first;nextstate = state;ok = true;for(j = 0; j < arr[i].size(); ++j){if((nextstate>>(arr[i][j]-'a'))&1)//該位存在{ok = false;break;}nextstate |= (1<<(arr[i][j]-'a'));}if(ok){dp[nextstate] = max(dp[nextstate], int(dp[state]+arr[i].size()));maxlen = max(maxlen, dp[nextstate]);}}}return maxlen;} };

184 ms 13.6 MB

總結

以上是生活随笔為你收集整理的LeetCode 1239. 串联字符串的最大长度（回溯/动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。