[LeetCode] 2707. Extra Characters in a String

https://leetcode.com/problems/extra-characters-in-a-string/description/?envType=daily-question&envId=2024-09-23

leetcode - Extra Characters in a String

문제 유형 : 문자열 처리, 재귀, dp

문제 난이도 : Medium

 

문제

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

 

0-index의 문자열 s와 단어 사전 dictionary가 주어집니다.

dictionary에 있는 단어들을 조합해서 s를 만들려 하는데, 일부 글자가 부족할 수 있습니다.

이에 대해서 글자 하나씩 추가하여 메꿀 수 있는데, 필요한 추가 글자의 개수의 최소값을 구하시오.

 

풀이

dfs와 dp를 이용해서 풀 수 있다.

dfs에는 남은 suffix와, dp테이블과 dictionary를 준다.

dp[len] = 남은 suffix의 len에서 최소 글자를 추가값이다.

 

만약 남은 suffix가 없다면, 0을 반환한다. 추가할 글자가 없기 때문이다.

dp테이블에 값이 있다면, dp값을 반환하여 중복 계산을 없앤다.

그게 아니라면, 직접 찾아야 한다.

만약 dictionary의 단어 중에서 suffix의 prefix가 될 수 있는 단어가 있다면, dfs를 타고 더 깊이 들어가서 최소값을 갱신한다.

현재 suffix의 맨 앞글자를 그냥 글자 1 추가하는거로 치고, 그 남은 suffix에서 dfs를 호출시켜서 또 최소값을 갱신한다.

이 값을 dp테이블에 저장하고 반환한다.

 

코드

C++

class Solution {
private:
    int dfs(const string &suffix, vector<string> &dictionary, unordered_map<int, int> &cache) {
        int len = suffix.size();
        if(len == 0) return 0;

        if(cache.find(len) != cache.end()) return cache[len];

        int minimum = len;
        for(const auto &word : dictionary) {
            if(suffix.substr(0, word.size()) == word){
                minimum = min(minimum, dfs(suffix.substr(word.size()), dictionary, cache));
            }
        }

        minimum = min(minimum, 1 + dfs(suffix.substr(1), dictionary, cache));

        cache[len] = minimum;
        return minimum;
    }

public:
    int minExtraChar(string s, vector<string>& dictionary) {
        unordered_map<int, int> cache;

        return dfs(s, dictionary, cache);
    }
};