Solution to JZ 58 II and LeetCode 844.
JZ 58 II
Left rotate a string (Medium). [link]
1] Slice and join.
Time complexity O(n), space complexity O(n).
class Solution:
def LeftRotateString(self , str: str, n: int) -> str:
if not str or len(str) == 0:
return ""
if n > len(str):
slice = n % len(str)
else:
slice = n
return str[slice:len(str)] + str[0:slice]
2] Iteration. When slicing is not allowed, we can iterate through the array and append values to a list.
Note that operating using Array is much more efficient than operating using String directly, because String object is immutable in python - each time a string is assigned to a variable a new object is created in memory to represent the new value.
Time complexity O(n), space complexity O(n).
class Solution:
def LeftRotateString(self , str: str, n: int) -> str:
if not str or len(str) == 0:
return ""
res = []
if n > len(str):
nn = n % len(str)
else:
nn = n
for i in range(nn, len(str)):
res.append(str[i])
for j in range(0,nn):
res.append(str[j])
return "".join(res)
# A simplified version using Modulo Operator.
class Solution:
def LeftRotateString(self , str: str, n: int) -> str:
res = []
for i in range(n, n + len(str)):
res.append(str[i % len(str)])
return ''.join(res)
LeetCode 844
Backspace String Compare (Easy) [link]
Simulating the typing process. Time complexity O(n+m) where n and m are the length of the two input strings. Space complexity O(1).
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def compare(string):
i = 0
res = ''
while i<len(string):
res = res + string[i]
if string[i] == "#":
res = res[:-2]
string = string[:i] + string[i+1:]
else:
i+=1
return res
return compare(s) == compare(t)
