6 ms C++ solution based on modified #320's generateAbbreviations (DFS, backtracking) and #408's validWordAbbreviation


  • 3
    A

    By applying following optimizations to reduce computations.

    1. filter words in dictionary with length different than target's;
    2. when generating abbreviations of target, stops when "length" of abbreviation is going to exceed the length of current best abbreviation;
    3. when generating abbreviations of target, starts with larger number first, then small number, then letter.
    class Solution {
    public:
        bool validWordAbbreviation(string &word, string &abbr) {
            int i = 0, j = 0, m = word.length(), n = abbr.length();
            while (i < m && j < n) {
                if (word[i] == abbr[j])
                    ++i, ++j;
                else if (abbr[j] == '0')
                    return false;
                else if (isdigit(abbr[j])) {
                    int len = 0;
                    while (j < n && isdigit(abbr[j]))
                        len = len * 10 + abbr[j++] - '0';
                    i += len;
                }
                else
                    return false;
            }
            return i == m && j == n;
        }
        
        void helper(vector<string> &dict, string &ans, int &ansLen, string &s, int len, string &word, int i) {
            if (i == word.length()) {
                if (len < ansLen) {
                    int valid = false;
                    for (string w : dict) {
                        if (validWordAbbreviation(w, s)) {
                            valid = true;
                            break;
                        }
                    }
                    
                    if (!valid) {
                        ansLen = len;
                        ans = s;
                    }
                }
                return;
            }
            
            if (len == ansLen)
                return;
            
            if (s.empty() || !isdigit(s.back())) {
                for (int j = word.length() - 1; j >= i; --j) {
                    int pos = s.length();
                    s += to_string(j - i + 1);
                    ++len;
                    helper(dict, ans, ansLen, s, len, word, j + 1);
                    --len;
                    s.erase(pos);
                }
            }
            
            s.push_back(word[i]);
            ++len;
            helper(dict, ans, ansLen, s, len, word, i + 1);
            --len;
            s.pop_back();
        }
    
        string minAbbreviation(string target, vector<string>& dictionary) {
            if (target.empty())
                return "";
            
            vector<string> dict;
            for (string word : dictionary) {
                if (word.length() == target.length())
                    dict.push_back(word);
            }
            
            string s, ans = target;
            int ansLen = target.length();
            helper(dict, ans, ansLen, s, 0, target, 0);
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.