4-5 lines Python solutions


  • 40

    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!


  • 0
    B

    @StefanPochmann said in 4-5 lines Python solutions:

    m.group(0)

    really good solution.But a little confused about the first solution:

    lambda m: str(len(m.group(0))) + m.group(1)

    how the expression get the parameter "m"?
    Please give a bit explaination, thank you.


  • 0
    C

    @StefanPochmann
    Thank you for the clean solution, I am do not understand the necessity of \2 in the regular expression in solution 2.
    What does it do? Why doesn't ((.)*) work? One () captures the entire group for len() to give the number of repetition, and the other () captures the number.


  • 0

    @chongkuan123 said in 4-5 lines Python solutions:

    @StefanPochmann
    Why doesn't ((.)*) work?

    Because that matches any amount of any characters, without caring whether they're the same. My ((.)\2*) on the other hand captures one character and then looks for more of that character.


Log in to reply
 

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