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

题目

https://leetcode.com/problems/contiguous-array/

题解

回溯法，每个字符串都有可能加或者不加。

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

总结

以上是生活随笔为你收集整理的leetcode 1239. Maximum Length of a Concatenated String with Unique Characters | 1239. 串联字符串的最大长度（回溯）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。