Python solutions


  • 9

    Solution 1

    I use product to generate masked words like "w##d" and then use sub to turn them into the desired format like "w2d".

    def generateAbbreviations(self, word):
        return [re.sub('#+', lambda m: str(len(m.group())), ''.join(masked))
                for masked in itertools.product(*(c+'#' for c in word))]
    

    Solution 2a

    Recursive, word[first:last+1] is the first part that I replace with a number.

    def generateAbbreviations(self, word):
        return [word] + [word[:first] + str(last - first + 1) + word[last+1:last+2] + rest
                         for last in range(len(word))
                         for first in range(last + 1)
                         for rest in self.generateAbbreviations(word[last+2:])]
    

    Solution 2b

    Similar to 2a, just a variation.

    def generateAbbreviations(self, word):
        return [word] + [word[:begin] + str(end - begin) + word[end:end+1] + rest
                         for begin, end in itertools.combinations(range(len(word)+1), 2)
                         for rest in self.generateAbbreviations(word[end+1:])]

  • 2
    J

    Another idea :)

    // In each slot, there is only 2 choice - keep the char or add to count
    string Parse(string word, int mask)
    {
    	string result;
    	int count = 0;
    	for (int i = word.size() - 1; i >= 0; i--)
    	{
    		if (mask % 2 == 1)
    			count++;
    		else
    		{
    			if (count > 0)
    				result = to_string(count) + result;
    			result = word[i] + result;
    			count = 0;
    		}
    		mask = mask >> 1;
    	}
    	if (count > 0)
    		result = to_string(count) + result;
    	return result;
    }
    
    vector<string> generateAbbreviations(string word) {
    	vector<string> result;
    	int size = word.size();
    	for (int i = 0; i < (1 << size); i++)
    		result.push_back(Parse(word, i));
    	return result;
    }
    

  • 1

    Gets "Wrong Answer". Fails the example input already.


  • 0
    J

    My bad, forgot to change the second last line code in Parse(); I have updated the code.


  • 1

    Wouldn't have happened if you weren't walking through the word backwards :-P

    Going forwards is much nicer anyway, then you can use a range-based loop and +=:

    string Parse(string word, int mask) {
        string result;
        int count = 0;
        for (char c : word) {
            if (mask & 1)
                count++;
            else {
                if (count)
                    result += to_string(count);
                result += c;
                count = 0;
            }
            mask >>= 1;
        }
        if (count)
            result += to_string(count);
        return result;
    }
    

  • 0
    J

    That is true. They are sort of identical, but I like your simple code. My code is the reflection of what I was thinking. :)


  • 0

    @StefanPochmann super cool solutions, I really dig the use of itertools.product() coupled with regexp.


Log in to reply
 

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