ValidWordAbbreviationOPT [source code]

public class ValidWordAbbreviationOPT {
static
/******************************************************************************/
public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i, j, count = 0;
        for (i = 0, j = 0; j < abbr.length(); j++) {
            char c = abbr.charAt(j);
            if (Character.isDigit(c)) {
                if (count == 0 && c == '0') return false;
                count = count * 10 + c - '0';
            } else {
                i += count;
                count = 0;
                if (i >= word.length() || word.charAt(i++) != c) return false;
            }
        }
        return i + count == word.length();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidWordAbbreviationOPT.Solution tester = new ValidWordAbbreviationOPT.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();
        }
    }
}

这个是submission最优解: 20(80). 不仅比我快的多, 而且还很简短;

看了一下代码, 这个代码确实是用最简练的方式表达了这个问题的思路了;
首先注意一个东西, 他这里这个算法(实质上是一个stream算法)同样是以判断entry为主: 按照entry的情况来区分逻辑上的两个branch;

另外, 我的算法当时的想法是希望让word和abbr尽可能相同速度的iterate; 他这里的想法则不是, 他让abbr稍微快一步, 只有当abbr的iteration已经获得了下一步i应该skip的步数, i才进行移动;
从另一个角度理解, 可以认为他的双循环的重点是abbr, 而我的abbr的重点其实是word, 或者说两者一样的重视程度;

不过理论上来说, 要是真的面试碰到这个问题, 写不出这么简练的代码并不过分, 但是就算是写我自己的那个代码, 最好还是基本功要练好. 说实话我自己的算法用到的功能其实都是我已经比较熟悉的功能了, 但是写起来还是磕磕巴巴. 你真的面试的时候写出来的代码verbose也不是不行, 但是你不能慢.

discussion上面也看了一些代码, 简练程度都不如这个代码;

Stefan的regex解:

I just turn an abbreviation like "i12iz4n" into a regular expression like "i.{12}iz.{4}n". Duh.

public boolean validWordAbbreviation(String word, String abbr) {  
    return word.matches(abbr.replaceAll("[1-9]\\d*", ".{$0}"));  
}

有空再看看就好了; 看了一下介绍算法核心其实也是差不多的;

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