LeetCode-1239

题目

1239. 串联字符串的最大长度

代码

思路：回溯

因为最终结果由子序列字符串连接而成，考虑到顺序和每个元素只能选取一次，以arr = ["un","iq","ue"]为例，可以画出这样的树状图：

遇到非法情况或递归到最后一个元素时，要回溯：

可以用一个集合set记录已有的字符。

PS：map是“引用类型”，对它的操作会影响到上一级函数

Set + Closure

func maxLength(arr []string) (ans int) {
	arr = removeRepeat(arr) // 去除自身包含重复项的元素

	// 使用魔法：closure
	var backtrack func(int, map[rune]bool)
	backtrack = func(index int, set map[rune]bool) {
		// 递归终止条件
		if index == len(arr) {
			ans = max(ans, len(set))
			return
		}

		str := arr[index]
		var repeat bool // 记录当前字符串是否和已有的相冲突
		for _, v := range str {
			if _, ok := set[v]; ok {
				repeat = true
			}
		}

		if !repeat {
			// map是“引用类型”，对它的操作会影响到上一级函数
			newSet := make(map[rune]bool)
			for k, v := range set {
				newSet[k] = v
			}
			for _, v := range str {
				newSet[v] = true
			}
			// 向下走
			backtrack(index+1, newSet)
		}
		// 向右走
		backtrack(index+1, set)
	}
	
	backtrack(0, make(map[rune]bool))
	return ans
}

// 去除自身包含重复项的元素
func removeRepeat(arr []string) (ans []string) {
	for _, s := range arr {
		flag := true
		set := make(map[rune]bool)
		for _, ch := range s {
			if _, ok := set[ch]; ok {
				flag = false
			} else {
				set[ch] = true
			}
		}
		if flag {
			ans = append(ans, s)
		}
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

位运算 + Closure

用一个二进制数字mask标记被选中的元素，如arr = ["un","iq","ue"]，mask = 101表示unue。

func maxLength(arr []string) (ans int) {
	// 筛选出无重复项的元素
	var masks []int
	for _, str := range arr {
		// 魔法：位运算，用第i位是否为1标识masks的第i个元素是否被选中
		mask := 0
		// 标记是否有重复的
		flag := true
		for _, ch := range str {
			// 输入为纯小写 a-z
			ch = ch - 'a'
			// 有冲突
			if mask>>ch&1 != 0 {
				flag = false
				break
			} else {
				mask |= 1 << ch
			}
		}
		if flag {
			masks = append(masks, mask)
		}
	}

	var backtrack func(int, int)
	backtrack = func(index int, mask int) {
		// 递归终止条件
		if index == len(masks) {
			ans = max(bits.OnesCount(uint(mask)), ans)
			return
		}

		s := masks[index]
		// 无冲突
		if s&mask == 0 {
			backtrack(index+1, mask|s)
		}
		backtrack(index+1, mask)
	}

	backtrack(0, 0)
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}