This Problem Can Benefit from a More Precise Definition


  • 0
    P

    I think the problem was not stated clearly enough. The only criterion listed is that the encodings of two word's can't be the same. For example, this does not make clear why, if we had two words that share the same initial encoding, we couldn't expand one more character of one of the words, and leave the other with its encoding.

    I wouldn't have known what was accepted as correct without trying different cases with the grader.

    Here's an example from the test cases:

    Submission Result: Wrong Answer More Details 
    
    Input:
    ["abcdefg","abccefg","abcckkg"]
    Output:
    ["abcd2g","abcc2g","a5g"]
    Expected:
    ["abcd2g","abccefg","abcckkg"]
    
    class Solution {
    public:
        vector<string> wordsAbbreviation(vector<string>& dict) {
            abbreviationSlots.clear();
            
            for (const auto &word : dict)
            {
                addWord(word, getBaseAbbrev(word));
            }
            
            unordered_map<string, string> wordToAbbrev;
            
            for (const auto &abbrevInfoSlotIter : abbreviationSlots)
            {
                for (const auto &abbrevInfo : abbrevInfoSlotIter.second)
                {
                    wordToAbbrev[abbrevInfo.word] = getAbbreviation(abbrevInfo.word, abbrevInfo.encodingLength);
                }
            }
            
            vector<string> result;
            
            result.reserve(dict.size());
            
            for (const auto &word : dict)
            {
                result.push_back(wordToAbbrev[word]);
            }
            
            return result;
        }
    
    private:
        class AbbreviationInformation
        {
        public:
            string word;
            int encodingLength;
            
            AbbreviationInformation(string word, int encodingLength)
            : word(word), encodingLength(encodingLength)
            {}
        };
        
        unordered_map<string, vector<AbbreviationInformation>> abbreviationSlots;
        
        void addWord(string word, string abbrev)
        {
            int maxEncodingLength = word.size() - 2;
            
            if (abbreviationSlots.count(abbrev))
            {
                //cout << "Abbrevation slot for " << abbrev << endl;
                for (auto &abbrevInfo : abbreviationSlots[abbrev])
                {
                    int length = getMaximumEncodingLength(word, abbrevInfo.word);
                    
                    abbrevInfo.encodingLength = min(length, abbrevInfo.encodingLength);
                    maxEncodingLength = min(length, maxEncodingLength);
                }
                abbreviationSlots[abbrev].emplace_back(word, maxEncodingLength);
            } else {
                vector<AbbreviationInformation> newSlot = { AbbreviationInformation(word, maxEncodingLength) };
                abbreviationSlots[abbrev] = newSlot;
            }
        }
        
        static string getBaseAbbrev(string word)
        {
            if (word.size() < 4)
            {
                return word;
            }
            
            string result;
            
            result.push_back(word[0]);
            result.append(to_string(word.size() - 2));
            result.push_back(word[word.size() - 1]);
            
            return result;
        }
        
        static string getAbbreviation(string word, int encodingLength)
        {
            string result;
            int prefixLength = word.size() - 1 - encodingLength;
            
            result.reserve(word.size() - encodingLength + 2);
            for (int c = 0; c < prefixLength; ++c)
            {
                result.push_back(word[c]);
            }
            result.append(to_string(encodingLength));
            result.push_back(word[word.size() - 1]);
            
            return result.size() >= word.size() ? word : result;
        }
        
        static int getCommonPrefixLength(string word1, string word2)
        {
            int length = min(word1.size(), word2.size());
            
            for (int i = 0; i < length; ++i)
            {
                if (word1[i] != word2[i])
                {
                    return i;
                }
            }
            
            return length;
        }
        
        static pair<string, string> getMinNonConflictingAbbrevs(string word1, string word2)
        {
            int commonPrefixLength = getCommonPrefixLength(word1, word2);
            string word1Encoding(word1.substr(0, commonPrefixLength + 1));
            
            word1Encoding.append(to_string(word1.size() - word1Encoding.size() - 1));
            word1Encoding.push_back(word1[word1.size() - 1]);
            
            if (word1Encoding.size() >= word1.size())
            {
                word1Encoding = word1;
            }
            
            string word2Encoding(word2.substr(0, commonPrefixLength + 1));
            
            word2Encoding.append(to_string(word2.size() - word2Encoding.size() - 1));
            word2Encoding.push_back(word2[word2.size() - 1]);
            
            if (word2Encoding.size() >= word2.size())
            {
                word2Encoding = word2;
            }
            
            return make_pair(word1Encoding, word2Encoding);
        }
        
        inline static int getMaximumEncodingLength(string word1, string word2)
        {
            int result = word1.size() - getCommonPrefixLength(word1, word2) - 2;
    
            //cout << "getMaximumEncodingLength(" << word1 << ", " << word2 << ") = " << result << endl;
    
            return result;
        }
    };
    

  • 0
    F

    I think that the sample input/output in the problem description gives an example of the situation you're describing.

    [... "intension", "face", "intrusion"] 
    [... "inte4n","f2e","intr4n"]
    

Log in to reply
 

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