string

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...

解法

class Solution(object):
def countAndSay(self, n):
    """
    :type n: int
    :rtype: str
    """
    prev = ""
    cur = "1"
    for i in range(n-1):
        prev = cur
        cur = ""
        cnt = 1
        for s in range(len(prev)):

            if s+1 < len(prev) and prev[s] == prev[s+1]:
                cnt += 1
            else:
                cur = cur + str(cnt) + str(prev[s])
                cnt = 1

    return cur

第二题 Implement strStr()

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

解法

class Solution(object):
def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    length1 = len(haystack)
    length2 = len(needle)
    if length2 == 0: return 0
    for i in range(length1 - length2 + 1):
        if needle == haystack[i:length2+i]:
            return i
    return -1

第三题 Group Anagrams

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

解法

class Solution(object):
def groupAnagrams(self, strs):
    """
    :type strs: List[str]
    :rtype: List[List[str]]
    """
    anas = {}
    for string in strs:
        s = ''.join(sorted(string))
        if s in anas:
            anas[s].append(string)
        else:
            anas[s] = [string]
    return [ anas[x] for x in anas ]

第四题 Simplify Path

解法

class Solution(object):
def simplifyPath(self, path):
    places = [p for p in path.split("/") if p!="." and p!=""]
    stack = []
    for p in places:
        if p == "..":
            if len(stack) > 0:
                stack.pop()
        else:
            stack.append(p)
    return "/" + "/".join(stack)

第五题 Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

解法

 class Solution(object):
def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    return str(int(num1)*int(num2))

第六题 Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

Note: A word is defined as a character sequence consists of non-space characters only.

解法

class Solution(object):
def lengthOfLastWord(self, s):
    """
    :type s: str
    :rtype: int
    """
    if not s: return 0

    line = s.split()

    if not line: return 0

    last = line[-1]
    return len(last)

第七题 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

解法

class Solution(object):
def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    s = s.lower()
    tmp = ''.join([c for c in s if c.isalnum()])
    if tmp[::-1] == tmp:
        return True
    return False

字符串

第一题 Count and Say

解法