[leetcode 3563][Go][动态规划]区间DP和线性DP的混合使用

题目链接

leetcode 3563 移除相邻字符后字典序最小的字符串

解题思路

暴力解法-深度遍历（超时）

遍历出字符串每种变化的可能并选出字典序最小的字符串，时间复杂度为$O(n * 2^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func compare(a *string, b *string) int {
	var i, j = 0, 0
	for i < len(*a) && j < len(*b) {
		if (*a)[i] != (*b)[j] {
			return int((*a)[i]) - int((*b)[i])
		}
		i++
		j++
	}
	if j >= len(*b) && i >= len(*a) {
		return 0
	} else if j >= len(*b) {
		return 1
	} else {
		return -1
	}
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func lexicographicallySmallestString(s string) string {
	var hash = make(map[string]bool)
	var ret = s
	var dfs func(*string, int)
	dfs = func(str *string, i int) {
		if i >= len(*str) {
			return
		}
		if i > 0 {
			x := abs(int((*str)[i]) - int((*str)[i-1]))
			if x == 1 || x == 25 {
				ns := (*str)[:i-1] + (*str)[i+1:]
				if !hash[ns] {
					hash[ns] = true
					if compare(&ns, &ret) < 0 {
						ret = ns
					}
					dfs(&ns, i-1)
				}
			}
		}
		dfs(str, i+1)
	}
	dfs(&s, 0)
	return ret
}

动态规划

首先需要设置两个dp数组dp1和dp2，dp1[i][j]表示[i, j]是否可以完全消除(-1表示不可消除，0表示未判断，1表示可完全消除)，dp2[i]表示s[i:]中移相邻字符后字典序最小的字符串

为什么要求s[i:]中字典序最小的字符串

根据字典序的比较原理，若s1比s2字典序小，那么s1[i:]的字典序也一定比s2[i:]的字典序小，例如s1 = “abcd”, s2 = “abce”，那么s1[1:] = “bcd”, s2[1:] = “bce”，所以s1[1:]比s2[1:]小

根据以上性质，可以设置dp从后往前逐个递推s[i:]的最小字符串(0 <= i < len(s))。

递推s[i:]时，分为以下两种情况

  1. s[i]属于答案中的字符，那么就可以直接加上后一位的最小字符串，即p2[i] = s[i] + dp2[i+1]，
  2. s[i]被消掉不属于答案中的字符，前提是至少存在一个j，使得[i,j]内的字符能够完全消除，即dp1[i][j] > 0，此时s[i:]的最小字符串等于s[j+1:]的最小字符串，即dp2[i] = dp2[j+1]

计算出上述两种情况的字符串后比较字典序最小的即为s[i:]中最小的字符串

如何计算[i,j]内的字符串是否能完全消除(求出dp1)

这里分出三种条件

  1. j-i == 1且s[i]与s[j]相邻，此时[i,j]可完全消除
  2. j-i > 1且(j-i-1)%2==0即s[i]和s[j]之前存在偶数个字符(两两消除若存在奇数个一定无法完全消除),若s[i]与s[j]相邻且s[i]与s[j]之间的字符串能完全消除，那么[i,j]就能完全消除
  3. 前提条件同样是j-i>1且(j-i-1)%2==0若存在一个k，使得[i,k]和[k+1,j]的字符串都能完全消除，那么[i,j]就能完全消除，例如”abef”，存在k=1使得[0,1]和[2,3]能够完全消除，所以”abef”能够完全消除

根据以上三个条件就能求出dp1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//判断ab是否为相邻字符
func isConsecutive(a uint8, b uint8) bool { 
	return a+1 == b || b+1 == a || (a == 'a' && b == 'z') || (a == 'z' && b == 'a')
}

func lexicographicallySmallestString(s string) string {
	s = "_" + s//防止-1越界，坐标从1开始
    //-1为无法完全消除，0表示未处理，1表示可以完全消除
	var dp1 = make([][]int8, len(s))
	for i := range dp1 {
		dp1[i] = make([]int8, len(s))
	}
	for j := 1; j < len(s); j++ {
		for i := j - 1; i > 0; i-- {
			switch {
            //条件1
			case j-i == 1 && isConsecutive(s[i], s[j]):
				dp1[i][j] = 1
			case j-i > 1 && (j-i-1)%2 == 0:
                //条件2
				if dp1[i+1][j-1] > 0 && isConsecutive(s[i], s[j]) {
					dp1[i][j] = 1
				}
                //条件3
                //因为两两消除[i,k]长度必定为偶数，每次步进2减少枚举次数
				for k := i + 1; k < j; k += 2 {
					if dp1[i][k] > 0 && dp1[k+1][j] > 0 {
						dp1[i][j] = 1
                        break
					}
				}
                //以上两种条件都不符合即判断无法消除
				if dp1[i][j] == 0 {
					dp1[i][j] = -1
				}
			default:
				dp1[i][j] = -1
			}
		}
	}

	var dp2 = make([]string, len(s)+1)//防止s[len(s)]越界
	dp2[len(s)] = ""
	for i := len(s) - 1; i > 0; i-- {
		res := s[i:i+1] + dp2[i+1]
        //枚举每个可以使[i,j]完全消除的可能
		for j := i + 1; j < len(s); j += 2 {
			if dp1[i][j] > 0 {
				res = min(res, dp2[j+1])
			}
		}
		dp2[i] = res
	}

	return dp2[1]
}

以上总时间复杂度为$O(n^3)$