題目敘述
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 <= 161 <= arr[i].length <= 26arr[i] contains only lower case English letters.
Hint 1:
You can try all combinations and keep mask of characters you have.
Hint 2:
You can use DP.
題目翻譯
給一個 list 參數 arr，其中元素都是字串。要從中找出最長的字串組合。其中這個組合要符合的條件，就是其中的元素需要是唯一的字母。
解法解析
大部分的解法，會用到位元運算子 <<、&、>>。有的則是單純的使用演算法比對長度的方式。個人覺得最漂亮的方式是 Swift 的解法。
使用兩個迴圈處理做 Dynamic programming，第一層去遍歷 arr 的元素，去跟另一層迴圈遍歷的 list combos 做判斷。如果 arr 和 combos 遍歷的元素相加後，是唯一的話，則儲存到 combos，並且跟最大值最比較。
程式範例
Python
Runtime Best
class Solution:
def maxLength(self, arr: List[str]) -> int:
def max_len_of_merged_word(words):
largest, M = 0, len(words)
for i in range(M):
word_set_1 = set(words[i])
size = len(words[i])
for j in range(M):
if j == i:
continue
word_set_2 = set(words[j])
if word_set_1.isdisjoint(word_set_2):
size += len(words[j])
word_set_1 = word_set_1.union(word_set_2)
largest = max(largest, size)
return largest
strs = [arr[i]
for i in range(len(arr)) if len(arr[i]) == len(set(arr[i]))]
return max(
max_len_of_merged_word(strs),
max_len_of_merged_word(sorted(strs, reverse=True)))
Memory Best
class Solution:
def maxLength(self, arr: List[str]) -> int:
return self.helper('', arr, 0)
def helper(self, curr, arr, idx):
res = len(curr)
if idx >= len(arr):
return res
for i in range(idx, len(arr)):
if not set(curr) & set(arr[i]) and (len(arr[i]) == len(set(arr[i]))):
res = max(res, self.helper(curr + arr[i], arr, i + 1))
return res
JavaScript
var maxLength = function (arr) {
let optSet = new Set();
for (let word of arr) optimize(optSet, word);
optArr = [...optSet];
return dfs(optArr, 0, 0);
};
const optimize = (optSet, word) => {
let charBitSet = 0;
for (let c of word) {
const mask = 1 << (c.charCodeAt() - 97);
if (charBitSet & mask) return;
charBitSet += mask;
}
optSet.add(charBitSet + (word.length << 26));
};
const dfs = (optArr, pos, res) => {
const oldChars = res & ((1 << 26) - 1),
oldLen = res >> 26;
let best = oldLen;
for (let i = pos; i < optArr.length; i++) {
const newChars = optArr[i] & ((1 << 26) - 1),
newLen = optArr[i] >> 26;
if (newChars & oldChars) continue;
const newRes = oldChars + newChars + ((oldLen + newLen) << 26);
best = Math.max(best, dfs(optArr, i + 1, newRes));
}
return best;
};
Go
func maxLength(arr []string) int {
c := []uint32{}
max := 0
for _, s := range arr {
var mask uint32
for _, c := range s {
mask = mask | 1<<(c-'a')
}
if len(s) != bits.OnesCount32(mask) {
continue
}
c = append(c, mask)
}
dfs(c, 0, 0, &max)
return max
}
func dfs(c []uint32, index int, mask uint32, max *int) {
*max = Max(*max, bits.OnesCount32(mask))
for i := index; i < len(c); i++ {
if mask&c[i] == 0 {
dfs(c, i+1, mask|c[i], max)
}
}
return
}
func Max(a, b int) int {
if a > b {
return a
}
return b
}
Swift
class Solution {
private func isUnique(_ str: String) -> Bool {
let set = Set<Character>(str)
return set.count == str.count
}
func maxLength(_ arr: [String]) -> Int {
var combos = [String]()
var maximum = 0
combos.append("")
for s in arr {
for c in combos {
let str = c + s
if isUnique(str) {
combos.append(str)
maximum = max(maximum, str.count)
}
}
}
return maximum
}
}
Kotlin
class Solution {
fun getMaxLength(
arr: List<String>,
charsInstring: Array<Int>,
uniqueLength: Int,
i: Int,
maxLengthTillNow: Int
): Int {
if (i >= arr.size) return maxLengthTillNow
var maxLength = 0
if (charsInstring[i] != -1 && charsInstring[i] and uniqueLength == 0) {
var includeLength =
getMaxLength(
arr,
charsInstring,
uniqueLength or charsInstring[i],
i + 1,
maxLengthTillNow + arr[i].length
)
maxLength = includeLength
}
var excludeLength = getMaxLength(arr, charsInstring, uniqueLength, i + 1, maxLengthTillNow)
maxLength = maxOf(maxLength, excludeLength)
return maxLength
}
fun maxLength(arr: List<String>): Int {
val charsInstring: Array<Int> = Array(arr.size) { 0 }
arr.forEachIndexed { index, word ->
var number = 0
var unique = true
word.forEach {
if (number and (1 shl (it - 'a')) != 0) {
unique = false
}
number = number or (1 shl (it - 'a'))
}
if (unique == false) {
charsInstring[index] = -1
} else {
charsInstring[index] = number
}
}
return getMaxLength(arr, charsInstring, 0, 0, 0)
}
}