Hypercube's LeetCode Weekly Contest 50

  • Rank: 183 / 2713
  • Score: 25 / 25
  • Finish Time: 01:55:22

Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
Accepted in 00:16:42 with 2 wrong submissions 
def check(s, e):
    left = 0
    right = len(s)-1
    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
            continue
        if e == 1:
            return False
        return check(s[left+1:right+1], 1) or check(s[left:right], 1)
    return True
class Solution:
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return check(s, 0)

Map Sum Pairs

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
Accepted in 00:19:25 
class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: void
        """
        self.d[key] = val

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        return sum(self.d[k] for k in self.d if k.startswith(prefix))


# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

  1. The string size will be in the range [1, 100].
Accepted in 00:24:33 
class Solution:
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        u, d = 0, 0
        for c in s:
            if c == '(':
                u += 1
                d += 1
                continue
            if c == ')':
                u -= 1
                d -= 1
                if u < 0:
                    return False
                if d < 0:
                    d = 0
                continue
            u += 1
            d -= 1
            if d < 0:
                d = 0
        return d == 0

24 Game

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

  1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
  3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.
Accepted in 01:15:22 with 6 wrong submissions 
s = {6667, 1557, 1558, 6677, 6678, 2599, 1577, 6699, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1119, 7777, 1122, 1123, 1124, 1125, 7778, 7779, 7788, 1133, 7789, 2677, 7799, 6777, 6778, 6779, 1667, 6788, 1159, 1677, 1678, 1167, 5777, 5778, 1177, 1178, 1179, 1189, 5799, 4779, 2222, 1199, 2226, 8888, 8889, 8899, 1222, 1223, 7888, 2777, 2779, 7899, 2279, 2799, 1777, 1778, 2299, 5899, 9999, 1299, 2334, 3358, 8999, 3388, 7999, 1355, 6999, 1899, 4459, 5999, 4466, 4467, 4999, 3467, 4499, 3488, 5557, 5558, 2999, 5569, 5579, 1999, 1499, 3555, 3577, 2555, 2556}
class Solution:
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        return nums[0] * 1000 + nums[1] * 100 + nums[2] * 10 + nums[3] not in s

'''My original program:
ls = [
    '((%d %s %d) %s %d) %s %d == 24',
    '%d %s ((%d %s %d) %s %d) == 24',
    '(%d %s (%d %s %d)) %s %d == 24',
    '%d %s (%d %s (%d %s %d)) == 24',
    '(%d %s %d) %s (%d %s %d) == 24',
]
ds = (
    (0, 1, 2, 3),
    (0, 1, 3, 2),
    (0, 2, 1, 3),
    (0, 2, 3, 1),
    (0, 3, 1, 2),
    (0, 3, 2, 1),
    (1, 0, 2, 3),
    (1, 0, 3, 2),
    (1, 2, 0, 3),
    (1, 2, 3, 0),
    (1, 3, 0, 2),
    (1, 3, 2, 0),
    (2, 1, 0, 3),
    (2, 1, 3, 0),
    (2, 0, 1, 3),
    (2, 0, 3, 1),
    (2, 3, 1, 0),
    (2, 3, 0, 1),
    (3, 1, 2, 0),
    (3, 1, 0, 2),
    (3, 2, 1, 0),
    (3, 2, 0, 1),
    (3, 0, 1, 2),
    (3, 0, 2, 1),
)
class Solution:
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        for l in ls:
            for o1 in '+-*/':
                for o2 in '+-*/':
                    for o3 in '+-*/':
                        for d1, d2, d3, d4 in ds:
                            try:
                                if eval(l % (nums[d1], o1, nums[d2], o2, nums[d3], o3, nums[d4])):
                                    return True
                            except:
                                pass
        return False
'''