Extra Characters in a String[Array,Hash Table,String,Dynamic Programming,Trie]

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

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.

 

Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

 

Constraints:

• 1 <= s.length <= 50
• 1 <= dictionary.length <= 50
• 1 <= dictionary[i].length <= 50
• dictionary[i] and s consists of only lowercase English letters
• dictionary contains distinct words

쉽지 않은 String 문제

Topic에 Dynamic programming이 있는 거부터 좀 짜증이 나긴 한다 ㅋㅋ

DP에 익숙해져야 한다..

 

1. Python

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        temp = 0
        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                if s[i:j] in dictionary:
                    temp += (j-i)
        return len(s)-temp

Hmm.. 처음에 이렇게 짜봤는데 dictionary에 substring이 여러개 있으면 중복으로 계산하는 걸 잡지 못한다.

 

결국 GPT Solution을 보게된 나. DP를 언제쯤 자유자재로 가지고 놀 수 있으려나 ㅠ

 

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        dp = [0] * (n+1) #dp[i] 는 s의 처음 i글자까지 최소 추가 가능한 문자의 수
        for i in range(1,n+1):
            dp[i] = dp[i-1] + 1 # i번째 문자를 추가 문자로 고려
            for word in dictionary:
                if i>=len(word) and s[i-len(word):i] == word :
                    dp[i] = min(dp[i],dp[i-len(word)])
        return dp[n]

 

2. C++

string.substr(a,b) => string의 a 지점에서 b만큼 잘라낸 substring을 반환한다.

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<int> dp(n+1,0);
        for(int i=1;i<=n;i++){
            dp[i] = dp[i-1] + 1;
            for(string const temp : dictionary){
                if(i>=temp.size() && s.substr(i-temp.size(),temp.size())==temp){
                    dp[i] = min(dp[i-temp.size()],dp[i]);
                }
            }
        }
        return dp[n];
    }
};

 

 

어렵다 어려워...