Strings
Loading
Loading
Strings
Counting characters, and why a bounded alphabet means constant space.
By the end of this chapter
def counts_of(text): counts = [0] * 26 for char in text: counts[ord(char) - ord("a")] += 1 return countsConcept
The array has 26 slots whether the string is ten characters or ten million. Space complexity measures growth with respect to the input, and this does not grow at all. State the alphabet bound when you make the claim — it is only true because the alphabet is fixed.
def same_letters(a, b): if len(a) != len(b): return False # free early exit counts = [0] * 26 for char in a: counts[ord(char) - ord("a")] += 1 for char in b: index = ord(char) - ord("a") counts[index] -= 1 if counts[index] < 0: return False # b needs a letter a ran out of return TrueSign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 2 practice problems.