2707. 字符串中的额外字符

2024-01-09 23:43:24

牛客网:https://leetcode.cn/problems/extra-characters-in-a-string/description/?envType=daily-question&envId=2024-01-09
在这里插入图片描述

官方解题思路为动态规划或字典数优化;
这里引入Up主的解题思路(递归)

哔哩哔哩:https://www.bilibili.com/video/BV1Ee41127LX/?spm_id_from=333.337.search-card.all.click&vd_source=f385259e95f72c4536cc27a3528bd922

Up主采用python3代码过题:

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:

        @cache
        def dfs(start):
            if start == len(s):
                return 0

            result = dfs(start + 1) + 1
            for end in range(start, len(s)):
                word = s[start: end + 1]
                if word not in dictionary:
                    continue
                result = min(result, dfs(end + 1))

            return result
        
        return dfs(0)

细看思路很简单,递归查找并比较所留最少字符的答案;
基于此思路,开启了Go语言的模仿:
第一反应,按照Up主的思路,直接dfs递归查找,结果当场TLE,debug发现,在回溯每个dfs,都会查找一次重复数据,于是开始剪枝优化

func minExtraChar(s string, dictionary []string) int {
	var dfs func(start int) int
	dfs = func(start int) int {
		if start == len(s) {
			return 0
		}
		result := dfs(start+1) + 1
		for end := start; end < len(s); end++ {
			word := s[start : end+1]
			for _, dic := range dictionary {
				if word != dic {
					continue
				}
				result = min(result, dfs(end+1))
			}
		}
		return result
	}
	return dfs(0)
}

AC代码:

func minExtraChar(s string, dictionary []string) int {
	cache := make(map[int]int)

	var dfs func(int) int
	dfs = func(start int) int {
		if start == len(s) {
			return 0
		}

		if val, ok := cache[start]; ok {
			return val
		}

		result := dfs(start+1) + 1
		for end := start; end < len(s); end++ {
			word := s[start : end+1]
			found := false
			for _, w := range dictionary {
				if word == w {
					found = true
					break
				}
			}
			if !found {
				continue
			}
			result = min(result, dfs(end+1))
		}

		cache[start] = result
		return result
	}

	return dfs(0)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

文章来源:https://blog.csdn.net/u012310622/article/details/135491239
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。