LicenseKeyFormatting [source code]

public class LicenseKeyFormatting {
static
/******************************************************************************/
class Solution {
    public String licenseKeyFormatting(String S, int K) {
        assert S.length () > 0 && K > 0;
        char[] chs = S.replace ("-", "").toUpperCase ().toCharArray ();
        int i = 0;
        StringBuilder sb = new StringBuilder ();
        if (chs.length > K) {
            int remainder = chs.length % K;
            while (i < remainder)
                sb.append (chs[i++]);
            if (sb.length () > 0)
                sb.append ('-');
            while (i < chs.length) {
                sb.append (chs[i]);
                if ((i + 1 - remainder) % K == 0 && i < chs.length - 1)
                    sb.append ('-');
                i++;
            }
        } else {
            sb.append (chs);
        }
        return sb.toString ();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LicenseKeyFormatting.Solution tester = new LicenseKeyFormatting.Solution();
        String[] inputs = {
            "5F3Z-2e-9-w", "4", "5F3Z-2E9W",
            "2-5g-3-J", "2", "2-5G-3J",
            "2", "2", "2",
            "a-a-a-a-", "1", "A-A-A-A",
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String S = inputs[3 * i], ans = inputs[3 * i + 2];
            int K = Integer.parseInt (inputs[3 * i + 1]);
            System.out.println (Printer.separator ());
            String output = tester.licenseKeyFormatting (S, K);
            System.out.printf ("%s and %d-> %s, expected: %s\n",
                S, K, Printer.wrapColor (output, output.equals (ans) ? "green" : "red"), ans
            );
        }
    }
}

题目本身看起来很简单, 不过AC rate并不高, 结合Google一贯的尿性, 估计有一些暗坑test; 不过还是先写;

Start from concrete

处理边界的时候, 直接笔算一个trace作为参考; 这个也是提醒过自己好几次了; 我这里用K等于3, chs长度为11来进行计算;

题目本身不难, 就在于细节处理上要小心一点, 最后写的时候果然是各种暗坑; 要是实际在Google面试的时候, 我这个分量, 估计还是不够吃的. 最后的速度是

注意这个API的使用:

java> sb.append (new char[]{'3'})  
java.lang.StringBuilder res2 = 123

本身简单的题目, 代码写的是否优雅就是比拼的对象了; 这个是discussion最优解:

@yuxiangmusic said in Java 5 lines clean solution:

    public String licenseKeyFormatting(String s, int k) {  
        StringBuilder sb = new StringBuilder();  
        for (int i = s.length() - 1; i >= 0; i--)  
            if (s.charAt(i) != '-')  
                sb.append(sb.length() % (k + 1) == k ? '-' : "").append(s.charAt(i));  
        return sb.reverse().toString().toUpperCase();  
    }

这个sb.length() % (k + 1) == k ? '-' : ""的使用非常的漂亮; 他的速度之所以快, 是因为他没有依赖于先找到S的长度, 而是直接1pass就搞定; 然而1pass做法的难度在于, 你怎么知道总长度呢? 解决这个问题的两个关键手段, 一个是反向扫, 一个是使用accumulator size, 这个其实是见到过的;

至于他这个巧妙的sb.length() % (k + 1) == k ? '-' : "", 你可以自己大概笔算一下(还是用"01234567890"这个例子, 不考虑'-')就知道是什么作用了;

看看这个trace:

i:(10), letter:(0) sb:(), sb.length:(0)  
i:(9), letter:(9) sb:(0), sb.length:(1)  
i:(8), letter:(8) sb:(09), sb.length:(2)  
i:(7), letter:(7) sb:(098), sb.length:(3)  
i:(6), letter:(6) sb:(0987), sb.length:(4)  
i:(5), letter:(5) sb:(0987-6), sb.length:(6)  
i:(4), letter:(4) sb:(0987-65), sb.length:(7)  
i:(3), letter:(3) sb:(0987-654), sb.length:(8)  
i:(2), letter:(2) sb:(0987-6543), sb.length:(9)  
i:(1), letter:(1) sb:(0987-6543-2), sb.length:(11)  
i:(0), letter:(0) sb:(0987-6543-21), sb.length:(12)

注意他这里的dash是作为一个prefix, 也就是先考虑是否append dash, 然后再append letter;

看看这个例子就知道为什么要%(k+1)了, 因为从第二个dash开始的append的判断, 是判断当前sb里面是否正好有multiple 4(-4)+这样的结构; 理解了这个正则, 这个问题就不难理解了; 当然, 对于第一个dash的理解, 也不难; 所以最后实际上就是判断4('-' 4)*这个正则;

另外, 想到反向扫的做法, 本身也不是特别难; 这一题本质上还是一个类似余数的问题, 余数问题把remainder部分放在最后去处理是一个很自然的思路, 往往能够让代码简化很多, 就跟这一题一样;

可以看到, 反向扫的另外一个好处就是自动解决了chs.length <= K这个问题;

这个是另外一个解法:

@zzhai said in Java 5 lines clean solution:

Found this little gem -
https://discuss.leetcode.com/topic/75225/java-easy-to-understand-solution

 public String licenseKeyFormatting(String S, int K) {  
    S = S.replaceAll("-", "").toUpperCase();  
    StringBuilder sb = new StringBuilder(S);  
    // Starting from the end of sb, and going backwards.   
    int i = sb.length() - K;  
    while(i > 0) {  
        sb.insert(i, '-');  
        i = i - K;  
    }  
    return sb.toString();  
}

这个小算法还真的是有点意思, 用gem来称呼完全不过分; 这个人看到了问题的核心本质, 本质不是build, 而是delete dash然后add dash;

这个是一个类似我的正向扫的做法, 不过他选择了用2pass, 虽然如此, 最后得到的代码非常容易理解, 而且不用专门处理K > length的情况:

@hemantpandey said in Easy to understand using StringBuilder:

public class Solution {  
    public String licenseKeyFormatting(String S, int K) {  
        // Replacing all - and converting all letters to uppercase  
        String S1 = S.replace("-","");  
        S1 = S1.toUpperCase();  

        // Making stringBuilder   
        StringBuilder sb = new StringBuilder();  
         for(int i=0; i<S1.length();i++) {  
            sb.append(S1.charAt(i));  
        }  
        int len = sb.toString().length();  
        // Inserting '-' from back at every K position  
        for(int i=K; i < len; i=i+K) {  
                sb.insert(len-i,'-');  
            }  
        return sb.toString();     
    }  
}

当然实际上第二个loop是没有必要的:

@zzzzzgo said in Easy to understand using StringBuilder:

@hemantpandey Maybe there is no need to go through S to build the StringBuilder? That will be more concise then.

public String licenseKeyFormatting(String S, int K) {  
    S = S.replace("-","").toUpperCase();  
    // Making stringBuilder   
    StringBuilder sb = new StringBuilder();  
    sb.append(S);  

    int len = S.length();  
    // Inserting '-' from back at every K position  
    for(int i=K; i < len; i=i+K) {  
            sb.insert(len-i,'-');  
    }  
    return sb.toString();     
}

submission最优解: 10(99):

class Solution {  
    public String licenseKeyFormatting(String s, int k) {  
        if(s.isEmpty()) {  
            return s;  
        }  
        char[] cs = s.toCharArray();  
        int newLen = cs.length + cs.length / k;  
        char[] result = new char[newLen];  
        int i = cs.length, j = result.length;  
        Loop:  
        for(char c;;) {  
            for(int m = 0; m < k;) {  
                if(--i < 0) {  
                    break Loop;  
                }  
                if((c = cs[i]) == '-') {  
                    continue;  
                }  
                if(c >= 'a' && c <= 'z') {  
                    c -= 32;  
                }  
                m++;  
                result[--j] = c;  
            }  
            result[--j] = '-';  
        }  
        if(j < result.length && result[j] == '-') {  
            j++;  
        }  
        return new String(result, j, result.length - j);  
    }  
}

造轮子的算法而已, 连 StringBuilder都不肯用, 非要用个array来搞, 大概看看就行了;

Problem Description

You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example 1:

Input: S = "5F3Z-2e-9-w", K = 4  

Output: "5F3Z-2E9W"  

Explanation: The string S has been split into two parts, each part has 4 characters.  
Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: S = "2-5g-3-J", K = 2  

Output: "2-5G-3J"  

Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Note:

• The length of string S will not exceed 12,000, and K is a positive integer.
• String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
• String S is non-empty.

Difficulty:Easy
Total Accepted:25.1K
Total Submissions:61.4K
Contributor:aizj_Forever
Companies
google