76. Minimum Window Substring

class Solution(object):
# O(n) O(n)
def minWindow(self, s, t):
# get counts of each character and length of t
need, missing = collections.Counter(t), len(t)
# initialize indice
i = I = J = 0
# loop s
for j, c in enumerate(s, 1):
# make sure only needed is reduced
missing -= need[c] > 0
# minus the count for every char
need[c] -= 1
if not missing:
# missing is zero
# left move to one of needed chars
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
# find min length
if not J or j - i <= J - I:
I, J = i, j
# return result
return s[I:J]
view raw 76_1014.py hosted with ❤ by GitHub

242. Valid Anagram

  • sort
  • hashmap
    class Solution(object):
    # O(nlogn)
    def isAnagram(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    ss = sorted(s)
    st = sorted(t)
    return ss == st
    view raw 242_1014.py hosted with ❤ by GitHub

139. Word Break

  • memo s[i:]
  • dp
    # memo string
    class Solution(object):
    def __init__(self):
    self.memo = dict()
    def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: List[str]
    :rtype: bool
    """
    if not s:
    self.memo[s] = True
    return True
    if s in self.memo:
    return self.memo[s]
    for i in range(len(s)):
    if s[:i+1] in wordDict and self.wordBreak(s[i+1:], wordDict):
    self.memo[s] = True
    return True
    self.memo[s] = False
    return False
    # memo start index
    class Solution(object):
    def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: List[str]
    :rtype: bool
    """
    memo = dict()
    return self.dfs(s, set(wordDict), 0, memo)
    def dfs(self, s, wordDict, start, memo):
    if start == len(s):
    return True
    if start in memo:
    return memo[start]
    for end in range(start+1, len(s)+1):
    if s[start:end] in wordDict and self.dfs(s, wordDict, end, memo):
    memo[start] = True
    return True
    memo[start] = False
    return False
    # dp
    class Solution(object):
    def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: List[str]
    :rtype: bool
    """
    wordSet = set(wordDict)
    dp = [False for i in range(len(s)+1)]
    # empty is True
    dp[0] = True
    # loop from 1 to len+1
    for i in range(1, len(s)+1):
    for j in range(i):
    # string 0 to i, split into 0 to j, and j+1 to i
    # since it's not zero based array, so we use [j:i]
    if dp[j] and s[j:i] in wordSet:
    dp[i] = True
    break
    # return
    return dp[len(s)]
    view raw 139_1014.py hosted with ❤ by GitHub

49. Group Anagrams

class Solution(object):
# O(nlgn*k) O(n*k)
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
groups = dict()
res = []
for s in strs:
sortedStr = "".join(sorted(s))
if sortedStr not in groups:
groups[sortedStr] = list()
groups[sortedStr].append(s)
return [v for _, v in groups.items()]
class Solution:
# O(n*k)
def groupAnagrams(strs):
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
ans[tuple(count)].append(s)
return ans.values()
view raw 49_1014.py hosted with ❤ by GitHub

387. First Unique Character in a String

# use dictionary
import collections
class Solution(object):
# O(n)
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
counts = collections.Counter(s)
for i, c in enumerate(s):
if counts[c] == 1:
return i
return -1
# use string count
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
letters='abcdefghijklmnopqrstuvwxyz'
index=[s.index(l) for l in letters if s.count(l) == 1]
return min(index) if len(index) > 0 else -1
view raw 387_1014.py hosted with ❤ by GitHub

283. Move Zeroes

class Solution(object):
# O(n) O(1)
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = 0
j = 0
while j < len(nums):
while i < len(nums) and nums[i] != 0:
i += 1
if j > i and nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i]
j += 1
class Solution(object):
# same method different way
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
lastNonZeroFoundAt = 0
for cur in range(len(nums)):
if nums[cur] != 0:
nums[cur], nums[lastNonZeroFoundAt] = nums[lastNonZeroFoundAt], nums[cur]
lastNonZeroFoundAt += 1
view raw 283_1014.py hosted with ❤ by GitHub