Extra Characters in a String

Leetcode Problem:

• Extra Characters in a String

Summary

• Given a string s and a dictionary of words, find the minimum number of extra characters left over if the string is broken into non-overlapping substrings present in the dictionary.

Approach

• Dynamic programming approach, where a 1D array dp is used to store the minimum number of extra characters for each prefix of the string
• The function go recursively tries to match the current prefix with each word in the dictionary, and updates the dp array accordingly.

Complexity

• O(n*m*len(word)) where n is the length of the string, m is the number of words in the dictionary, and len(word) is the length of each word in the dictionary.

Explain

• The function go takes a string s, a dictionary of words dict, and an integer i as input
• It first checks if the current prefix of the string has been processed before (i.e., dp[i] is not -1)
• If not, it sets dp[i] to 1 (for the extra character) and recursively calls itself for the next character
• Then it tries to match the current prefix with each word in the dictionary, and updates dp[i] with the minimum of its current value and the result of the recursive call for the next character plus the length of the current word
• The function minExtraChar initializes the dp array and calls the function go with the initial prefix as an empty string.

Solution Code:

class Solution {
public:
    int dp[51];
    int go(string & s, vector& dict, int i){
        if(i == s.size()) return 0;

        if (dp[i] == -1){
            dp[i] = 1 + go(s, dict, i+1);
            for(auto &w: dict){
                if(s.compare(i, w.size(), w) == 0){
                    dp[i] = min(dp[i], go(s, dict, i+w.size()));
                }
            }
        }
        return dp[i];

    }
    int minExtraChar(string s, vector& dictionary) {
        memset(dp, -1, sizeof(dp));
        return go(s, dictionary, 0);
    }
};