Java 15ms naive solution with some notes.


  • 0

    I think people know that some communication protocols use 8 '0' to encode a sequence of messages. But the length of those messages is fixed. For this problem, the length of each string can be different. Since of that, the basic idea is to add the length of those strings to the encoded string. And then add a sign other than 0-9 to mark the end of the length string.

    For the decoding procedure. Some people asked in other topics what if there are the same characters in the string which is used as the sign of the end of the length. The encoded string is something like length + 'sign' + original string + length + 'sign' + original string. So the length is read first. Then, skip one single sign character and read length-long string. Everything is fixed. For instance, if the encoded string is "2***", (I use * as the sign.) it points to the length-two string "**". That is the only interpretation.

    ps: The reason to use StringBuilder not just String to encode the strings is because append operation for StringBuilder is much faster than + operation for String.

    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(String str:strs){
            int len = str.length();
            StringBuilder marker = new StringBuilder();
            marker.append(len); marker.append("*");
            sb.append(marker); sb.append(str);
        }
        return sb.toString();
    }
    
    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        int curr = 0;
        List<String> ret = new ArrayList<>();
        int start = 0;
        int end = 0;
        while(curr<s.length()){
            int lenstart = curr;
            while(s.charAt(curr)<='9'&&s.charAt(curr)>='0'){
                curr++;
            }
            start = curr+1;
            end = start+Integer.valueOf(s.substring(lenstart,curr));
            ret.add(s.substring(start,end));
            curr = end;
        }
        return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.