b******i
发帖数: 914 | 1 Abbreviation: apple can be abbreviated to 5, a4, 4e, a3e, …
Given a target string (internationalization), and a set of strings,
return the minimal length of abbreviation of this target string so that it
won’t conflict with abbrs of the strings in the set.
“apple”, [“blade”] -> a4 (5 is conflicted with “blade”)
“apple”, [“plain”, “amber”, “blade”] -> ???
Problem changed to:
If given a string and an abbreviation, return if the string matches abbr.
“internationalization”, “i5a11o1” -> true
以前网友面经总结里面好几次出现，求解 | m******a
发帖数: 84 | | m*****k
发帖数: 731 | 3 抛砖：
public static boolean isAbbr(String s, String abbr){
//internationalization”, “i5a11o1”
if(s==null){
return abbr==null;
}
if(s.length()==0){
return abbr.length()==0;
}
abbr+="A";
int lastCharIdxInAbbr = -1;
int lastCharIdxInS = -1;
for(int i = 0; i
if(Character.isLetter(abbr.charAt(i))){
String numStr = abbr.substring(lastCharIdxInAbbr+1, i);
lastCharIdxInAbbr = i;
int num = 0;
if(numStr!=null&& numStr.length()>0){
num += Integer.parseInt(numStr);
}
lastCharIdxInS+=1+num;
if(i==abbr.length()-1){
return lastCharIdxInS == s.length();
}
else{
if(lastCharIdxInS>=s.length()){
return false;
}
if(s.charAt(lastCharIdxInS)!=abbr.charAt(
lastCharIdxInAbbr)){
return false;
}
}
}
}
return true;
} | m*****k
发帖数: 731 | 4 “apple”, [“blade”] -> a4 (5 is conflicted with “blade”)
“apple”, [“plain”, “amber”, “blade”] -> ???
all the input words same size?
it would simply the coding if so. | b******i
发帖数: 914 | 5 应该不是，应该是任意给一个字典，求某个单词的最短缩写
【在 m*****k 的大作中提到】
: “apple”, [“blade”] -> a4 (5 is conflicted with “blade”)
: “apple”, [“plain”, “amber”, “blade”] -> ???
: all the input words same size?
: it would simply the coding if so.
| m*****k
发帖数: 731 | | b******i
发帖数: 914 | | m*****k
发帖数: 731 | 8 把我那块砖的‘A'换成100，再小改改就成了。
【在 b******i 的大作中提到】
: 这个好像是两个不同的题
| b******i
发帖数: 914 | 9 了解，你做的是第二问。谢谢！
第一问感觉更challenging一些，还找到MIT300题上的一个原题:
给一字典,求其中某单词的最短缩写。比如internationalization可以缩写为i18n而不
产生歧义。 举例:一字典有6个单词:
hello
world
would
lord
hell
language
依次可以缩写为 hello -> 4o or h4 world -> 2r2 would -> 2u2 lord -> l3 or 3d
hell -> 3l or h3 language -> 8
【在 m*****k 的大作中提到】
: 把我那块砖的‘A'换成100，再小改改就成了。
| d******o
发帖数: 13 | |
|
