[LeetCode 2707] Extra Characters in a String

2707. Extra Characters in a String

주어진 문자열에서 dictionary에 존재하는 string과 매칭시켜, 매칭되지 않은 최소 문자 개수를 구하는 문제

📌 문제 개념

s = "leetscode"
dictionary = ["leet", "code", "leetcode"]

• 가능한 나누는 방법
  1. "leet" + "s" + "code" → "s"만 사전에 없음 → 추가 문자 개수 = 1
  2. "leetcode" + "s" → "s"만 사전에 없음 → 추가 문자 개수 = 1
  3. "l" + "eet" + "s" + "code" → "l", "eet", "s"가 사전에 없음 → 추가 문자 개수 = 3

📌 접근 방식

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50

1. 제약 사항을 보면 알겠지만 굉장히 숫자가 작다. 사실상 브루트 포스로 해결해도 될 것이라고 생각을 하였는데, 겹치지 않고 dictionary 에 존재하는 문자열로 제거하는 것을 떠올리는 것이 쉽지 않았다.

2. 구하려는 답이 사용되지 않는 문자의 개수를 최소화 하는 것이므로, 이를 dp배열로 나타내면 쉽게 해결할 수 있을 것이라고 생각했다.

   dp[i] : i번째 index까지 사용되지 않은 문자의 개수의 최소 값

3. 처음에는 단순히 현재 index까지의 문자열에 dictionary가 포함되어 있다면 해당 길이 만큼 빼주면서 dp배열을 계산했다.

   • 이는 물론 올바르지 않은 접근인데, subString은 여러개의 dictionary가 겹칠 가능성이 있다. 하지만 이에 대한 처리가 불가능하다.

   for(int i = 1; i <= s.length(); i++) {
             dp[i] = dp[i-1] + 1;
             string subStr(s.begin(), s.begin() + i); // 현재까지의 전체 부분 문자열
             for(int j = 0; j < dictionary.size(); j++) {
                 if(subStr.find(dictionary[j]) != string::npos) { // 사전 내 단어가 포함되어 있는지 확인
                     dp[i] = min(dp[i - dictionary[j].size()], dp[i]);
                 }
             }
         }

4. 그렇다면, 문제 제약사항도 널널하겠다. 그냥 string을 전부 순회하면서 각 string의 subString을 모두 확인하여 dictionary에 존재하는지 확인하면서 dp 배열을 계산해나갔다.

   • 현재 index까지의 모든 subString을 구한 뒤 dictionary에 존재한다면, 해당 길이 만큼 빼주면서 dp배열을 계산해나갔다.

   	for(int i = 1; i<=s.length(); i++){
           dp[i] = dp[i-1] + 1;
           for(int len  = 1; len <= i ; len++){
               string subStr = s.substr(i - len, len);
               if(dicSet.count(subStr)){
                   dp[i] = min(dp[i], dp[i - subStr.size()]);
               }
           }
       }

📌 정답

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int dp[51];
        dp[0] = 0;

        set<string> dicSet(dictionary.begin(), dictionary.end());

        for(int i = 1; i<=s.length(); i++){
            dp[i] = dp[i-1] + 1;
            for(int len  = 1; len <= i ; len++){
                string subStr = s.substr(i - len, len);
                if(dicSet.count(subStr)){
                    dp[i] = min(dp[i], dp[i - subStr.size()]);
                }
            }
        }

        return dp[s.length()];
    }
};