Abbreviation

408 Valid Word Abbreviation

Given a non-empty string word and an abbreviation abbr, return whether the string matches with the given abbreviation.

Example 1:

Given s = "internationalization", abbr = "i12iz4n": Return true.

Example 2:

Given s = "apple", abbr = "a2e": Return false.

• 注意第一次跟之後的number判斷不一樣

def validWordAbbreviation(self, word: str, abbr: str) -> bool:
    if not abbr:
        return not word
    if not word:
        return False
    
    if abbr[0].isalpha():
        if abbr[0] != word[0]: return False
        else:
            return self.validWordAbbreviation(word[1:], abbr[1:])
    else:
        num = int(abbr[0])
        # cornor case 
        # ['a'], ['01']
        if num == 0: return False
        i = 1
        while(i < len(abbr) and abbr[i].isdigit()):
            num = num*10 + int(abbr[i])
            i+=1
        return num <= len(word) and self.validWordAbbreviation(word[num:], abbr[i:])

320. Generalize Abbreviation

Write a function to generate the generalized abbreviations of a word.

Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", 
"w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1",
"3d", "w3", "4"]

def generateAbbreviations(self, word: str) -> List[str]:
    def backtrack(idx, count, abbr):
        # reach end, append abbr to result
        if idx == len(word):
            if count:
                abbr+=str(count)
            ans.append(abbr)
            
        else:
            # skip current character
            backtrack(idx+1, count+1, abbr)
            if count:
                abbr+=str(count)
            # include current character, set count to zero
            backtrack(idx+1, 0, abbr + word[idx])
    
    ans = []
    backtrack(0, 0, '')
    return ans 

527 Word Abbreviation

Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.

Begin with the first character and then the number of characters abbreviated, which followed by the last character. If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words. If the abbreviation doesn't make the word shorter, then keep it as original.

• Heap

• int array record the prefix

public String[] wordsAbbreviation(String[] dict) {
    int len = dict.length;
    String[] ans = new String[len];
    int[] pre = new int[len];
    Map<String, Integer> map = new HashMap<>();
    for(int i=0; i<len; i++){
        String abbr = helper(dict[i], 1);
        ans[i] = abbr;
        map.put(abbr, map.getOrDefault(ans[i], 0)+1);
        pre[i]=1;
    }

    while(true){
        boolean flag = true;
        for(int i=0; i<len; i++){
            if(map.get(ans[i]) > 1){
                flag = false;
                String abbr = helper(dict[i], ++pre[i]);
                ans[i] = abbr;
                map.put(abbr, map.getOrDefault(ans[i], 0)+1);
            }
        }
        if (flag == true) break;
    }
    return ans;
}

private String helper(String s, int start){
        if(s.length()-start <= 2){
            return s;
        }
        String middle = s.substring(start, s.length()-1);
        return s.substring(0, start) + middle.length() + s.charAt(s.length()-1);
    }