Given an array of strings arr
. String s
is a concatenation of a sub-sequence of arr
which have unique characters.
Return the maximum possible length of s.
Example 1:
Input: arr = ["un","iq","ue"] Output: 4 Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique". Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible solutions are "chaers" and "acters".
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
-
arr[i]
contains only lower case English letters.
串联字符串的最大长度。
给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是DFS backtracking。这里我用一个 letters 数组判断当前拼凑出来的 path 里面是否有重复字母,其他部分基本是标准的DFS。
时间O(n*2^n)
空间O(n)
Java实现
1 class Solution { 2 int res = 0; 3 4 public int maxLength(List<String> arr) { 5 // corner case 6 if (arr == null || arr.size() == 0) { 7 return 0; 8 } 9 dfs(arr, "", 0); 10 return res; 11 } 12 13 private void dfs(List<String> arr, String path, int index) { 14 boolean isUnique = helper(path); 15 if (isUnique) { 16 res = Math.max(res, path.length()); 17 } 18 if (index == arr.size() || !isUnique) { 19 return; 20 } 21 for (int i = index; i < arr.size(); i++) { 22 dfs(arr, path + arr.get(i), i + 1); 23 } 24 } 25 26 private boolean helper(String s) { 27 boolean[] letters = new boolean[26]; 28 for (int i = 0; i < s.length(); i++) { 29 if (letters[s.charAt(i) - 'a'] == true) { 30 return false; 31 } 32 letters[s.charAt(i) - 'a'] = true; 33 } 34 return true; 35 } 36 }