LeetCode 1239. 串联字符串的最大长度（回溯/动态规划）

示例 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] 中只含有小写英文字母

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'));
	    		}
    		}
    	}
    }
};

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()); //该单词选
    }
};

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 MB
                state = 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;
    }
};