Reverse Count and Say


  • 0
    D

    Hi,

    I was recently asked the following question: Given an input string which is the output of a count and say method, return the original number.

    For example: If the number if "21", then the count and say method would return
    "1211" (one two, one one). In this problem, the input provided to us is "1211" and our goal is to return "21".

    I answered this question by approaching it as a variant of the WordBreak problem with a dynamic programming solution. Of course, the conditions to check the validity of the split string will differ. Thoughts?


  • 0
    C

    @deeptigp
    public static void main(String arg[]){
    String number ="1211";
    StringBuffer st = new StringBuffer();
    for (int i=1;i<number.length();){

            char co = (number.charAt(i-1));
            int count = Character.getNumericValue(co);
            char letter = number.charAt(i);
            for (int j=0;j<count;j++){
                st.append(letter);
            }
            i=i+2;
        }
        System.out.println(st);
    }

  • 0
    def solution(num):
        # handle bad input
        if not num or len(str(num)) % 2 != 0:
            return None
    
        # list of digits
        nums = list(str(num))
        res = ''
    
        # visit even indices (the count portion of the pair)
        for i in range(0,len(nums),2):
            # add the number portion of the pair count times
            for _ in range(int(nums[i])):
                res += nums[i+1]
    
        return int(res)
    

  • 0
    M

    @deeptigp I agree with you that this could be solved in a similar way to word break problem. In my solution above, we need to call the recursive function twice (once for left and once for right substrings), which is the main difference with the word break problem. The reason is that as we segment the given string into two parts we cannot immediately tell what number a segment represents. Therefore, we need to recursively solve each subproblem. Let me know if you agree. I assume that if there is a solution, it must be unique. Below function could be optimized via memoization, but I left it out for brevity.

    def reversecount(s):
        if not s: return ''
        if '0' in s: return ''
        if len(s) == 1: return ''
        if len(s) == 2:
            return s[1]*int(s[0])
        if len(3) == 3:
            return s[2]*int(s[:2])
        n = len(s)
        for i in xrange(2,n-1):  ## go thru each possible segment
            left = reversecount(s[:i])    ## check if the left substring could produce a valid number
            right = reversecount(s[i:])  ## check if the right substring could produce a valid number
         ## if both substrings produce a valid number, then we found the original number
            if left and right: 
                return left + right
        return ''
    

Log in to reply
 

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