LeetCode 2707. 字符串中的额外字符 C#
原题链接
中等
作者:
hpstory
,
2023-06-02 22:27:00
,
所有人可见
,
阅读 202
C# 代码
public class Solution {
public int MinExtraChar(string s, string[] dictionary) {
int n = s.Length;
HashSet<string> set = dictionary.ToHashSet<string>();
int[] cache = new int[n];
Array.Fill(cache, -1);
return DFS(n - 1);
int DFS(int i){
if (i < 0) return 0;
if (cache[i] != -1) return cache[i];
cache[i] = DFS(i - 1) + 1;
for (int j = i; j >= 0; j--){
string t = s.Substring(j, i - j + 1);
if (set.Contains(t)){
cache[i] = Math.Min(cache[i], DFS(j - 1));
}
}
return cache[i];
}
}
}