Replace all occurrences of a space inside an array

Problem

Given an array of characters, replace all occurrences of a space with another string. Assume that the array has enough space to contain all of the replacements.

Input

• A - An array of characters which may or may not have spaces
• word - The string to replace spaces with.

Approach

The brute force solution for this problem is to allocate a new array \(B\), and add each non-space character occurrence in A into \(B\). If we do encounter a space character, we simply add all characters in word into \(B\), and then proceed with the iteration of the rest of the characters in A.

Optimization

The above approach is most likely not efficient enough, as allocating a new array can be costly in space.

Instead, the better way is to count the number of spaces, and determine where the last character will be in the final array, after the replacements are inserted. We can set this index pointer to \(p_{final}\).

Then, find the last non-null character in A, which is the original size of the string in A (we do not want to include the empty null characters in A). We can set this index pointer to \(p{last}\). Once we find these two sizes, we can then copy the character at \(p{last}\) into \(p{final}\), and decrement both \(p{last}\) and \(p{final}\). When \(p{last}\) is a space character, we add the word string character-by-character at \(p_{final}\), before resuming the former logic.

Solution

# assumes that A has enough space to contain the words
def replace_all(A, word):  
    # count blanks
    blanks = 0
    size = 0
    for i, c in enumerate(A):
        if c == ' ':
            blanks += 1
        elif c is None:
            break
        size += 1

    last_char_ptr = size
    final_char_ptr = final_size = size + ((len(word) - 1) * blanks)

    while last_char_ptr > 0:
        if A[last_char_ptr] != ' ':
            A[final_char_ptr] = A[last_char_ptr]
            final_char_ptr -= 1
        else:
            ctr = len(word) - 1
            while ctr >= 0:
                A[final_char_ptr] = word[ctr]
                ctr -= 1
                final_char_ptr -= 1

        last_char_ptr -= 1

    return "".join(A[:final_size])