leetcode 1239. Maximum Length of a Concatenated String with Unique Characters | 1239. 串联字符串的最大长度（回溯）

向右看齐 2022-09-12 08:49 179阅读 0赞

## 题目 ##

[https://leetcode.com/problems/contiguous-array/][https_leetcode.com_problems_contiguous-array]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

回溯法，每个字符串都有可能加或者不加。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        int N;
    
        public int maxLength(List<String> arr) { 
            N = arr.size();
            return process(arr, 0, 0, new boolean[26]);
        }
    
        public int process(List<String> arr, int i, int unique, boolean[] seen) { 
            if (i == N) return unique;
    
            String s = arr.get(i);
            int p1 = process(arr, i + 1, unique, seen); // 不加当前位置字符串
            int p2 = 0;
            if (isUnique(s, seen)) { 
                addString(s, seen);
                p2 = process(arr, i + 1, unique + s.length(), seen); // 加当前位置字符串
                delString(s, seen); // backtrace
            }
            return Math.max(p1, p2);
        }
    
        public boolean isUnique(String s, boolean[] seen) { 
            boolean[] self = new boolean[26];
            for (int i = 0; i < s.length(); i++) { 
                if (self[s.charAt(i) - 'a'] || seen[s.charAt(i) - 'a']) return false;
                self[s.charAt(i) - 'a'] = true;
            }
            return true;
        }
    
        public void addString(String s, boolean[] seen) { 
            for (int i = 0; i < s.length(); i++) { 
                seen[s.charAt(i) - 'a'] = true;
            }
        }
    
        public void delString(String s, boolean[] seen) { 
            for (int i = 0; i < s.length(); i++) { 
                seen[s.charAt(i) - 'a'] = false;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_contiguous-array]: https://leetcode.com/problems/contiguous-array/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d083fb9b128a45fe8a9da7636afff1d4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/a0c1514b43254967a6ec6bd426aa64de.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/0f31c61b890144a4b6e50debd2ab48c3.png