【leetcode】1239. Maximum Length of a Concatenated String with Unique Characters

题目如下：

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中有重复字符的元素，接下来就可以采用BFS的方法进行计算了。怎么判断两个字符串是否有相同字符呢？我的方法是把字符串转成二进制的方式，a对应2^0,c对应2^2,z对应2^25。这样的话，每一个字符串都可以计算出一个特征值，判断两个字符串是否有相同字符，只有判断两个特征值与操作的结果是否为0即可。

代码如下：

class Solution(object):

    def maxLength(self, arr):

        """

        :type arr: List[str]

        :rtype: int

        """

        arr_val = []

        for i in arr:

            val = 0

            if len(set(list(i))) != len(i):continue

            for j in i:

                val |= 2**(ord(j) - ord('a'))

            arr_val.append(val)

        #print arr_val

        queue = []

        if len(arr_val) == 0:return 0

        for (inx,val) in enumerate(arr_val):

            queue.append((inx,val))

        res = 0

        while len(queue) > 0:

            inx,val = queue.pop(0)

            end = True

            for i in range(inx+1,len(arr_val)):

                if val & arr_val[i] != 0:continue

                queue.append((i,val | arr_val[i]))

                end = False

            if end :

                res = max(res,bin(val).count(''))

        return res

巴特西

【leetcode】1239. Maximum Length of a Concatenated String with Unique Characters

最新文章

热门文章