ValidWordAbbreviation [source code]
public class ValidWordAbbreviation {
static
/******************************************************************************/
public class Solution {
public boolean validWordAbbreviation(String word, String abbr) {
if (word.length() == 0 && abbr.length() == 0) return true;
if (word.length() < abbr.length() || word.length() == 0 || abbr.length() == 0) return false;
String[] strW = word.split("");
String[] strA = parseAbbr(abbr);
int i = 0, j = 0;
while (i < strW.length && j < strA.length) {
if (strW[i].equals(strA[j])) {
i++;
j++;
} else {
try {
int skip = Integer.parseInt(strA[j]);
if (!strA[j].equals(Integer.toString(skip))) return false;
i += skip;
j++;
} catch (Exception e) {
return false;
}
}
}
return i == strW.length && j == strA.length;
}
public String[] parseAbbr(String abbr) {
char[] chs = abbr.toCharArray();
List<String> res = new ArrayList<>();
if (chs.length == 0) return new String[0];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < chs.length; i++) {
if (chs[i] < 'a') { //is number
if ((i < chs.length - 1 && chs[i + 1] >= 'a') || i == chs.length - 1) {
res.add(sb.toString() + chs[i]);
sb.setLength(0);
} else {
sb.append(chs[i]);
}
} else { //is not number
res.add(String.valueOf(chs[i]));
}
}
return res.toArray(new String[0]);
}
}
/******************************************************************************/
public static void main(String[] args) {
ValidWordAbbreviation.Solution tester = new ValidWordAbbreviation.Solution();
String[] inputs = {
"word", "1ord", "1",
"word", "w2d", "1",
"word", "w1r1", "1",
"word", "4", "1",
"internationalization", "i12iz4n", "1",
"apple", "a2e", "0",
"hi", "1", "0",
"hi", "02", "0",
};
for (int i = 0; i < inputs.length / 3; i++) {
String word = inputs[3 * i];
String abbr = inputs[1 + 3 * i];
boolean expected = inputs[2 + 3 * i].equals("1");
System.out.println(Printer.seperator());
Printer.openColor("magenta");
System.out.print(word + " AND " + abbr);
Printer.closeColor();
boolean output = tester.validWordAbbreviation(word, abbr);
System.out.print(" -> " + output);
Printer.openColor(output == expected ? "green" : "red");
System.out.println(", expected: " + expected);
Printer.closeColor();
}
}
}
这个题目其实思路非常简单, 就是一个跳子的思路, 只不过实现起来并没有那么trivial, 各种考察基本功, 这很Google;
关于split的一个小知识点:
java> "".split("").length
java.lang.Integer res1 = 1
java> "a".split("").length
java.lang.Integer res2 = 1
java> "ab".split("").length
java.lang.Integer res3 = 2
可以看到split("")出来的length是不可靠的; 尤其是上面这两个都是1的情况;
分段题, 先判断entry再判断flag;(是这样吗? 好像先判断flag好一些?)
不过这一题其实用分段思路来做不好, 因为分段题我们关心的其实只有段落以内的, 也就是波峰波谷, 我们只关注波峰. 这里的最好用边沿判断的思路来做: 波峰和波谷都要考虑; 传统的流算法就可以做了, 实现起来实际上反而更简单; 具体的思路就是一个伸脚探路的思路;
不过真正的段落算法其实判断的也是上升沿和下降沿? 而且主要工作量其实集中在下降沿.
主函数里面的循环是一个双iterator循环, 这种同是iterate两个及以上array的, 直接用while循环来写好像直观一些;
return i == strW.length && j == strA.length;
这一句还是挺有讲究的, 这个问题一个比较出问题的地方就在流尾的处理上面, 无论是i还是j, 都有可能会过冲 (如果abbr里面的数字不够, j就有可能第一个达到strA.length提前结束; 如果abbr里面有一个数字特别大, 那么i就会被过冲). 所以最后一定要判断两个都是和平结束(都是等于length的结束)才能说明整个循环走完是没有问题的;
最后的速度是35ms (6%), 有点失望; 感觉可能是各种JAVA自带的API用的太多了: exception, StringBuilder, list, Integer.parse;
这个是discussion上面一个跟我的做法比较类似的(iterate same speed at both arrays)解, 不过他写的还是简化很多, 虽然代码本身有些地方写的有点丑:
public boolean validWordAbbreviation(String word, String abbr) {
int i = 0, j = 0;
while (i < word.length() && j < abbr.length()) {
if (word.charAt(i) == abbr.charAt(j)) {
++i;++j;
continue;
}
if (abbr.charAt(j) <= '0' || abbr.charAt(j) > '9') {
return false;
}
int start = j;
while (j < abbr.length() && abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
++j;
}
int num = Integer.valueOf(abbr.substring(start, j));
i += num;
}
return i == word.length() && j == abbr.length();
}
这是另一个, 代码写的好看一些:
public boolean validWordAbbreviation(String word, String abbr) {
int number = 0;
int i = 0, j = 0;
while (i < word.length() && j < abbr.length()) {
if (Character.isDigit(abbr.charAt(j))) {
number = number * 10 + abbr.charAt(j) - '0';
if (number == 0) return false;
j++;
} else {
i += number;
if (i >= word.length() || word.charAt(i) != abbr.charAt(j)) return false;
number = 0;
i++; j++;
}
}
i += number;
return i == word.length() && j == abbr.length();
}
他这里对leading0的判断比较简练;
Problem Description
Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.
A string such as "word" contains only the following valid abbreviations:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".
Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.
Example 1:
Given s = "internationalization", abbr = "i12iz4n":
Return true.
Example 2:
Given s = "apple", abbr = "a2e":
Return false.
Difficulty:Easy
Total Accepted:10.3K
Total Submissions:37K
Contributor: LeetCode
Companies
google
Related Topics
string
Similar Questions
Minimum Unique Word Abbreviation Word Abbreviation