String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the “compressed” string would not become smaller than the original string, your method should returnthe original string. You can assume the string has only uppercase and lowercase letters (a - z).1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 # -*- coding:utf-8 -*-
class Zipper:
def zipString(self, iniString):
# write code here
zipStr = ""
strCnt = 1
for i in range(len(iniString) - 1):
if iniString[i + 1] == iniString[i]:
strCnt += 1
else:
zipStr += iniString[i] + str(strCnt)
strCnt = 1
zipStr += iniString[-1] + str(strCnt)
return zipStr if len(zipStr) < len(iniString) else iniString
URLify: Write a method to replace all spaces in a string with ‘%20: You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the “true” length of the string.1
2
3
4
5 # -*- coding:utf-8 -*-
class Replacement:
def replaceSpace(self, iniString, length):
# write code here
return iniString.replace(" ","%20")
Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18# -*- coding:utf-8 -*-
class Clearer:
def clearZero(self, mat, n):
# write code here
row = set()
col = set()
for r, m in enumerate(mat):
for c, n in enumerate(m):
if not n:
row.add(r)
col.add(c)
for r in row:
for i in range(len(mat[r])):
mat[r][i] = 0
for c in col:
for i in range(len(mat)):
mat[i][c] = 0
return mat
String Rotation: Assume you have a method isSubst ring which checks if one word is a substring of another. Given two strings, 51 and 52, write code to check if 52 is a rotation of 51 using only one call to isSubstring (e.g., “waterbottle “ is a rotation of “erbottlewat”).1
2
3
4
5# -*- coding:utf-8 -*-
class ReverseEqual:
def checkReverseEqual(self, s1, s2):
# write code here
return set(s1)==set(s2)