Java encoding using a "#" as delimiter and a length field. Ask on an onsite interview.


  • 0
    Y

    Used a length field separated by "#" from the String to encode and decode. For decode, I used recursion, iterative method is also easy to write.

    I'm also wondering is there any other way to avoid using the delimiter. I got asked this question on an interview, and they want a method without using a delimiter, kindly ask if anybody has an easy method of achieving it.

    public class Codec {
    
        // Encodes a list of strings to a single string.
        public String encode(List<String> strs) {
            StringBuilder sb = new StringBuilder();
            for(String str : strs) {
                int len = str.length();
                sb.append(len).append("#").append(str);
            }
            return sb.toString();
        }
    
        // Decodes a single string to a list of strings.
        public List<String> decode(String s) {
            List<String> res = new ArrayList<>();
            if(s == null || s.length() == 0) {
                return res;
            }
            
            int index = s.indexOf("#");
            int len = Integer.valueOf(s.substring(0, index));
            String t = s.substring(index + 1, index + 1 + len);
            res.add(t);
            res.addAll(decode(s.substring(index+1+len)));
            return res;
        }
    }

  • 2
    S

    One way, although not as efficient, is to reserve 10 chars to store the length for each string. For example:

    "abcd" ---> "0000000004abcd"

    "aaa.....a" ---> "0000099999aaa....a" if the string length is 99999

    A way to improve over this approach is to first go through the list and find the max length of strings. Then the number of characters you want to reserve for the count will be the number of digits in the max length.
    For example, if max length is 2567, then you only need to reserve 4 characters.


  • 0
    O

    very nice answer


Log in to reply
 

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