4-5 lines Python solutions


  • 33

    Solution 1 ... using a regular expression

    def countAndSay(self, n):
        s = '1'
        for _ in range(n - 1):
            s = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), s)
        return s
    

    Solution 2 ... using a regular expression

    def countAndSay(self, n):
        s = '1'
        for _ in range(n - 1):
            s = ''.join(str(len(group)) + digit
                        for group, digit in re.findall(r'((.)\2*)', s))
        return s
    

    Solution 3 ... using groupby

    def countAndSay(self, n):
        s = '1'
        for _ in range(n - 1):
            s = ''.join(str(len(list(group))) + digit
                        for digit, group in itertools.groupby(s))
        return s

  • 0
    G

    It's amazing !!! However, I'm confused about regular expression. Could you give me some explanation?


  • 0

    (.) captures one character and \1* covers its repetitions.


  • -1
    X

    thank you !but I run it in eclipse .
    as this:
    import re
    class Solution(object):
    def countAndSay(self, n):
    """
    :type n: int
    :rtype: str
    """
    s = '1'
    for _ in range(n-1):
    s = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), s)
    return s

    a=Solution()
    b=a.countAndSay(11)
    print b

    but the answer is 11131221133112132113212221
    so I am very puzzled.I need you help.


  • 0

    You didn't run it like that. Because that doesn't run at all, as it's not formatted properly.

    And 11131221133112132113212221 is the correct answer.


  • 0
    P

    @StefanPochmann Can you please explain the second solution a bit?


  • -1
    K

    @StefanPochmann

    Java solution, 4ms, clean code:

    public class Solution {
        public String countAndSay(int n) {
            if (n <= 1) {
                return "1";
            }
            
            String curr = "1";
            for (int i = 1; i < n; i ++) {
                curr = say(curr);
            }
            
            return curr;
        }
        
        private String say(String value) {
            StringBuilder builder = new StringBuilder();
            
            char character = 0;
            int count = 0;
            for (char c : value.toCharArray()) {
                if (c != character) {
                    if (count != 0) {
                        builder.append(String.valueOf(count));
                        builder.append(character);
                    }
                    character = c;
                    count = 1;
                } else {
                    count ++;
                }
            }
            
            if (count != 0) {
                builder.append(String.valueOf(count));
                builder.append(character);
            }
            
            return builder.toString();
        }
    }
    

  • 0

    Great solution! I used a negative lookahead with backreference to split at cluster boundaries. Here is the JavaScript:

    var countAndSay = function(n) {
        let res = '1';
        for (let i = 1; i < n; i++) {
            res = res.replace(/(\d)(?!\1)/g, '$1|').split('|').reduce((res, s) => res + (s ? s.length + s[0] : ''), '');
        }
        return res;
    };
    

  • 0
    I

    Hi there.

    In the 2nd solution, why using two pairs of brackets?
    If I remove the outer \1 brackets, there's ValueError from str.join() function, saying need more than 1 value to unpack. How did you use an (useless may not be the right word) extra brackets to satisfy str.join() argument requirements.

    Can you help explain this, please? Anybody?

    Thank you


  • 0
    W

    groupby is a really good thought!


Log in to reply
 

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