Leetcode 1239. 串联字符串的最大长度（DAY 112）---- 回溯算法学习期

原题题目

代码实现（首刷超时 TLE 85\85)

class Solution {
    
public:void backtracking(vector<bool>& visit,const vector<string>& arr,int& ret,int pos,int size){
    ret = max(ret,size);for(int i=pos;i<arr.size();++i){
    int stopsize = 0,flag = 0;for(const auto&chr:arr[i]){
    if(visit[chr-'a']){
    flag = 1;break;}visit[chr-'a'] = true;++stopsize;}for(int j=0;flag && j<stopsize;++j) visit[arr[i][j]-'a'] = false;if(!flag){
    backtracking(visit,arr,ret,i+1,size+arr[i].size());for(const auto& chr:arr[i])   visit[chr-'a'] = false;}backtracking(visit,arr,ret,i+1,size);}}int maxLength(vector<string>& arr) {
    vector<bool> visit(26,false);int ret = 0;backtracking(visit,arr,ret,0,0);return ret;}
};

代码实现（首刷优化）

class Solution {
    
public:void backtracking(int& m,const vector<string>& arr,int& ret,int pos,int size){
    ret = max(ret,size);auto temp = m;for(int i=pos;i<arr.size();++i){
    int flag = 0;for(const auto&chr:arr[i]){
    if(m & (1<<(chr-'a'))){
    flag = 1;break;}m |= (1<<(chr-'a'));}if(!flag)   backtracking(m,arr,ret,i+1,size+arr[i].size());backtracking(temp,arr,ret,i+1,size);}}int maxLength(vector<string>& arr) {
    int visit = 1<<26;int ret = 0;backtracking(visit,arr,ret,0,0);return ret;}
};