522. 最长特殊序列 II.md

522. 最长特殊序列 II

题目传送门

点击这里

解题思路

这道题可以通过暴力LCS来做，LCS可以看一下1143. 最长公共子序列，题意非常难理解而且还有误，这道题其实是求最大的字符串长度，且该字符串满足要求不是其他字符串的子序列即可，所以可以直接暴力LCS即可。

代码

func findLUSlength(strs []string) int {
	var res = -1
	n := len(strs)
	for i := 0; i < n; i++ {
		if len(strs[i]) < res {
			continue
		}
		ok := true
		for j := 0; j < n && ok; j++ {
			if i == j {
				continue
			}
			ok = !check(strs[i], strs[j])
		}
		if ok {
			res = len(strs[i])
		}
	}
	return res
}

func check(s1, s2 string) bool {
	n1, n2 := len(s1), len(s2)
	if n1 > n2 {
		return false
	}
	dp := make([][]int, n1+1)
	for i := range dp {
		dp[i] = make([]int, n2+1)
	}
	for i := 1; i <= n1; i++ {
		for j := 1; j <= n2; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			}else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
			if dp[i][j] == n1 {
				return true
			}
		}
	}
	return false
}

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

}