Tag: strings

Python: String Compression

The idea of string compression is as follows: AAAB > A3B1. That is, if we’re given 3 A’s and 1 B, the output should be A3B1.

If we go by this logic, for input of AAABaaaaAA, we should get A5B1a4. This can be achieved by the code given below:

# string compression problem
# AAAB > A3B1

def compress_string(s):
    
    temp = {}
    for letter in s:
        if letter in temp:
            temp[letter] += 1
        else:
            temp[letter] = 1
            
    compressed_string = ''
    
    for letter in temp:
        compressed_string += letter + str(temp[letter])
        
    return compressed_string

compress_string('AAABaaaaAA') #Output: A5B1a4

The code starts with a temp dictionary. It then looks at each letter in the input string and counts it using temp.

Next it simply concatenates letter (the actual character) and str(temp[letter]) (the count of that character) in a variable called compressed_String and prints it.

Python: Sentence Reversal

In the previous post I wrote about reversing a word or an input string. In this one, let’s look at reversing a sentence. For example: “landed has Eagle The” should become “The Eagle has landed”.

To achieve this we’re going to build on top of the string reversal code from the previous post.

def reverse_word(word):
    
    letters = list(word)
    start = 0
    end = len(letters)-1
    
    while start < end:
        letters[start], letters[end] = letters[end], letters[start]
        start+=1
        end-=1
        
    return ''.join(letters)

def reverse_sentence(words):
    
    # reverse the whole string -- # O(n)
    words = reverse_word(words) 
    
    # convert string to a list
    temp = words.split(' ')
    
    # reverse each word in that list -- # O(n)
    for i in range(len(temp)):
        temp[i] = reverse_word(temp[i]) 
        
    # the above loop is O(n) 
    # because we only go through every letter once
        
    # convert list to a string and return it
    return ' '.join(temp)
    
reverse_sentence('landed has Eagle The') #Output: The Eagle has landed

In the code above, we accept an input string, use the string reversal function to reverse it. This gets us ehT elgaE sah dednal as the output and we store it in temp by splitting it at spaces.

The next step is to use string reversal code again but this time we use it for each word and that gets us our intended output, which is: The Eagle has landed.