I have written a solution to the question: "You are given a non-empty string, and a key, k which is a positive integer value. You are asked to shift each character in string by k values across according to the alphabet."
For example, if k=2 and string = "abcd" -> "cdef". And we need to **wrap around the alphabet ** for any order greater than 'z'. i.e. if string= "zzz" and k=2 then the output should be "bbb".
My solution uses a dictionary to store the ord() of all characters in the alphabet, then for each character in string simply adds k to the order and returns the corresponding character from the dictionary:
def caesarCipherEncryptor(string, key):
my_dict = dict()
for i in range(97, 123):
my_dict[ord(chr(i)) - ord("a")] = chr(i)
res = ""
for i in range(len(string)):
finder = (ord(string[i]) - ord("a")) + key
while finder > 25:
finder = finder % 26
res += my_dict[finder]
return res
The code above passes all test cases presented, so that is no issue. However,I am told that the optimum space complexity for this problem is O(n), however by the way I have solved it in the above, is it not O(1)? Since I am simple storing all characters in the alphabet (max 26) in my dictionary?
The space complexity is O(n) because if there were more letters to the alphabet, or you were trying to extend this program you would have to insert all those letters too. Thus, for a problem space of n letters, you are using n bytes of space which means the space complexity is O(n)