Straightforward Python

  • 9

    It not stated in the question but you can assume there is not invalid operations, such as C when the points history is empty, it still passed.

    class Solution(object):
        def calPoints(self, ops):
            # Time: O(n)
            # Space: O(n)
            history = []
            for op in ops:
                if op == 'C':
                elif op == 'D':
                    history.append(history[-1] * 2)
                elif op == '+':
                    history.append(history[-1] + history[-2])
            return sum(history)

  • 1

    Hi @wanling, I came up with a very similar solution in C++. I agree with you, that it is more simple and efficient to calculate the sum after the entire string has been processed, rather than keeping track of a running total. Since the calculations for the running total could be all for nothing, if we end up invalidating all (or a significant portion) of the input using op "C".

    Also, I've had great success rates following the advice I found from @StefanPochmann, specifically: "Knowing and using library functions can do miracles for you. It's fast to use them and they probably don't have bugs."
    ( ). I'd like to dedicate this solution to Stefan, thanks so much Stefan for continually sharing your quality of thought!

    class Solution{
        int calPoints(vector<string>& ops){
            vector<int> r{};
            for (string& op : ops){
                if      (op=="C"){ r.pop_back(); }
                else if (op=="D"){ r.push_back(2*r.back()); }
                else if (op=="+"){ r.push_back(r.end()[-2]+r.end()[-1]); }
                else             { r.push_back(stoi(op)); }
            return accumulate(r.begin(), r.end(), 0);

  • -1

    Good logic. But could be more preventive.

    With operation C, you need to make sure your stack is not empty before doing pop. Otherwise, you will receive IndexError

    With D and + operation, you can go out of range and get IndexError.

  • 0

    @Free9 thanks, I agree with you... actually I had a try/catch in my original code, I removed it to see if there were any invalid input test cases, and there are none. In a real-world use case, definitely I would have kept it. For LeetCode purposes, it can be distracting to add checks for invalid input.

  • 3

    Simply add two 0 at the left of the input list would solve this problem.

  • 0

    @tndstone That's a good idea! 😃

  • 0

    @wanling The question should state clearly that C won't appear when there's no valid points, and + won't appear when there're not enough valid points. I was worried about the same thing when I hit submit.

Log in to reply

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