In [1]:
from __future__ import print_function
from __future__ import division
from __future__ import absolute_import
from __future__ import unicode_literals
In [2]:
def isUnique(string):
return len(set(string)) == len(string)
In [6]:
def isUnique(string):
charMap = {}
for char in string:
if char in charMap:
return False
charMap[char] = True
return True
In [4]:
def isUnique(string):
charList = []
for char in string:
if char in charList:
return False
charList.append(char)
return True
In [7]:
for string in ['abc', 'aacc']:
print("'{}' => {}".format(string, isUnique(string)))
In [5]:
## use sorted
def arePermutations(stringA, stringB):
return sorted(stringA) == sorted(stringB)
In [8]:
## use character map
def charMap(string):
return dict([(char, True) for char in string])
def arePermutations(stringA, stringB):
return charMap(stringA) == charMap(stringB)
In [9]:
for (stringA, stringB) in [
('abc', 'cba'),
('abc', 'abc '),
('abc', 'Abc'),
('acc', 'xyz')
]:
print("('{}', '{}') => {}".format(stringA, stringB, arePermutations(stringA, stringB)))
In [10]:
def URL(string, length):
return string[:length].replace(' ', '%20')
In [11]:
for (string, length) in [('Mr John Smith ', 13), ('Somebody here ', 13)]:
print("('{}', {}) => '{}'".format(string, length, URL(string, length)))
In [12]:
from collections import defaultdict
def freqMap(string):
freq = defaultdict(int)
for char in string:
if char.strip() != '':
freq[char.lower()] += 1
return freq
def isPalindromPermutation(string):
freq = freqMap(string)
return len([x for x in freq.values() if x == 1]) == 1 and max(freq.values()) <= 2
In [13]:
for string in [
'Tact Coa',
'abc ba',
'xilin sun',
'lucky li'
]:
print("'{}' => {}".format(string, isPalindromPermutation(string)))
In [14]:
## solution 1: check by edit type: replace or insert
def oneReplaceAway(s1, s2):
return sum([s1[i] != s2[i] for i in range(len(s1))]) < 2
def oneInsertAway(s1, s2):
foundDifference = False
iA, iB = 0, 0
while iA < len(s1) and iB < len(s2):
if s1[iA] != s2[iB]:
if foundDifference:
return False
foundDifference = True
iA += 1
continue
iA += 1
iB += 1
return True
def oneAway(s1, s2):
if abs(len(s1) - len(s2)) >= 2:
return False
if len(s1) == len(s2):
return oneReplaceAway(s1, s2)
if len(s1) > len(s2):
return oneInsertAway(s1, s2)
return oneInsertAway(s2, s1)
In [16]:
## don't check edit type
def oneAway(s1, s2):
if abs(len(s1) - len(s2)) >= 2:
return False
if len(s1) < len(s2):
s1, s2 = s2, s1
foundDifference = False
iA, iB = 0, 0
while iA < len(s1) and iB < len(s2):
if s1[iA] != s2[iB]:
if foundDifference:
return False
foundDifference = True
if len(s1) != len(s2):
iA += 1
continue
iA += 1
iB += 1
return True
In [17]:
for (s1, s2) in [
('abc', 'abc'),
('ple', 'pale'),
('pale', 'ple'),
('pale', 'bale'),
('pale', 'bake')
]:
print("'{}', '{}' => {}".format(s1, s2, oneAway(s1, s2)))
In [99]:
def compressed(string):
charList = []
i = 0
while i < len(string) - 1:
j = i + 1
while j < len(string):
if string[i] == string[j]:
j += 1
else:
break
charList.append("{}{}".format(string[i], j - i))
i = j
compressedString = "".join(charList)
if len(compressedString) < len(string):
return compressedString
return string
In [19]:
## check in advance
def compressedLen(string):
count = 1
for i in range(len(string) - 1):
if string[i+1] != string[i]:
count += 1
return count * 2
def compressed(string):
if len(string) <= compressedLen(string):
return string
charList = []
i = 0
while i < len(string) - 1:
j = i + 1
while j < len(string):
if string[i] == string[j]:
j += 1
else:
break
charList.append("{}{}".format(string[i], j - i))
i = j
return "".join(charList)
In [20]:
for string in [
'aabcccccaaa',
'abcdefg',
'',
'IkeoIIkkkkkeo',
'AbOOOOook'
]:
print("'{}' => '{}'".format(string, compressed(string)))
In [21]:
def rotated(matrix):
N = len(matrix)
nLayers = int(N / 2)
for i in range(nLayers):
for j in range(i, N - 1 -i):
matrix[i][j], matrix[j][N - i - 1], matrix[N - i - 1][N - j - 1], matrix[N - j - 1][i] = matrix[N - j - 1][i], matrix[i][j], matrix[j][N - i - 1], matrix[N - i - 1][N - j - 1]
return matrix
In [22]:
from pprint import pprint
matrix = [
['aa', 'kk', 'ac', 'oo'],
['cc', 'oc', 'lo', 'ls'],
['mf', 'wy', 'xr', 'wk'],
['ss', 'fs', 'pz', 'dg']
]
pprint(matrix)
print("=>")
pprint(rotated(matrix))
In [26]:
# duplicate the matrix
# O(MN) space
from copy import deepcopy
def zeroMatrixIndex(matrix, x, y):
newMatrix = deepcopy(matrix)
N, M = len(matrix), len(matrix[0])
for i in range(N):
newMatrix[i][y] = 0
for j in range(M):
newMatrix[x][j] = 0
return newMatrix
def zeroMatrix(matrix):
newMatrix = deepcopy(matrix)
N, M = len(matrix), len(matrix[0])
for i in range(N):
for j in range(M):
if matrix[i][j] == 0:
newMatrix = zeroMatrixIndex(matrix, i, j)
return newMatrix
In [24]:
# solve in-place:
def zeroMatrix(matrix):
N, M = len(matrix), len(matrix[0])
# log if the first row and col contains zeros
# save in two variables
zeroInRow0 = 0 in matrix[0]
zeroInCol0 = 0 in [row[0] for row in matrix]
# log other zeroes and save in the first row and col
for i in range(1, N):
for j in range(1, M):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# assign rows
for i in range(1, N):
if matrix[i][0] == 0:
matrix[i] = [0 for x in range(M)]
# assign cols
for j in range(1, M):
if matrix[0][j] == 0:
for i in range(N):
matrix[i][j] = 0
return matrix
In [27]:
matrix = [
[4, 1, 3],
[1, 0, 5],
[9, 10, 3],
[8, 2, 3]
]
from pprint import pprint
pprint(matrix)
print("=>")
pprint(zeroMatrix(matrix))
In [28]:
def isSubstring(s1, s2):
return s1 in s2
def isRotation(s1, s2):
return isSubstring(s1, s2 * 2)
In [29]:
for (s1, s2) in [
('waterbottle','erbottlewat'),
('abc', 'bca'),
('adasf', 'asasdfaq')
]:
print("('{}', '{}') => {}".format(s1, s2, isRotation(s1, s2)))
In [ ]: