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.
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);
}