Hadron DaVinci

Reverse Position of All Letters Except Symbols

19 Dec 2020 - Hadron DaVinci

Problem

Given a string, reverse the position of every letter in that string except non-letters.

Examples

foo('a#') == 'a#'

foo('#a') == '#a'

foo('ab#') == 'ba#'

foo('a#b') == 'b#a'

foo('#ab') == '#ba'

foo('ab,c,de!$') == 'ed,c,ba!$'

Assumption

• In the reversed string the index of symbols remains unchanged

---

Methods

Method 1

Time Complexity: O(k*N)

• k represents the number of symbols present
• where 0 <= k <= N

Spatial Complexity: O(N)

Method 1 Summary

1. parse input backwards to get reversed order of non symbols
   • let’s call this result rws (Reversed Without Symbols)
2. parse input forwards and insert symbols into rws

Method 1 Solution

def foo(a: str):
    rws = []
    a_last_index = len(a) - 1

    index = a_last_index
    while index >= 0:               # loop backwards and build rws
        element = a[index]
        if element.isalpha():
            rws.append(element)
        index -= 1

    index = 0
    while index <= a_last_index:    # loop forwards and insert symbols
        element = a[index]
        if not element.isalpha():
            rws.insert(index, element)
        index += 1
    return ''.join(rws)

# Try Code
if __name__ == "__main__":
   assert foo('a#') == 'a#'
   assert foo('#a') == '#a'
   assert foo('ab#') == 'ba#'
   assert foo('a#b') == 'b#a'
   assert foo('#ab') == '#ba'
   assert foo('ab,c,de!$') == 'ed,c,ba!$'

---

Method 2

Time Complexity: O(N)
Spatial Complexity: O(N)

Method 2 Summary

1. Create a left and right index
   • initialize left_index at 0
   • initialize right index at len(a)
     
     
2. While left_index < right_index do the following
   • move left_index to closest non symbol
     • must increment up
   • move right_index to closest non symbol
     • must increment down
   • swap elements at left and right indices

Method 2 Solution

def get_left_index(a: str):
    """
    Generator finds index of letters while incrementing left to right
    """
    left_index = 0
    while left_index < len(a):
        element = a[left_index]
        if element.isalpha():
            yield left_index
        left_index += 1

def get_right_index(a: str):
    """
    Generator finds index of letters while incrementing right to left
    """
    right_index = len(a) - 1
    while right_index >= 0:
        element = a[right_index]
        if element.isalpha():
            yield right_index
        right_index -= 1

def foo(a: str) -> str:
    a = list(a)
    left_iterator = get_left_index(a)
    right_iterator = get_right_index(a)
    left_index = next(left_iterator)
    right_index = next(right_iterator)

    while left_index < right_index:
        a[left_index], a[right_index] = a[right_index], a[left_index]      # swap elements at left and right indices
        left_index = next(left_iterator)                                   # get the next letter from left side
        right_index = next(right_iterator)                                 # get the next letter from right side

    return ''.join(a)

# Try Code
if __name__ == "__main__":
   assert foo('a#') == 'a#'
   assert foo('#a') == '#a'
   assert foo('ab#') == 'ba#'
   assert foo('a#b') == 'b#a'
   assert foo('#ab') == '#ba'
   assert foo('ab,c,de!$') == 'ed,c,ba!$'

---

Method 3

Time Complexity: O(N)
Spatial Complexity: O(N)

Method 3 Summary

1. Create a left and right index
   • initialize left_index at 0
   • initialize right index at len(a)
     
     
2. While left_index < right_index do the following
   • If a[left_index] is symbol
     • skip it by incrementing left_index
   • else If a[right_index] is symbol
     • skip it by decrementing right_index
   • else both must a[left_index] and a[right_index] must be both non-symbols
     • swap elements at left and right indices
     • increment left_index
     • decrement right index

Method 3 Solution

def foo(a: str) -> str:
    a = list(a)
    left_index = 0
    right_index = len(a) - 1

    while left_index < right_index:
        if not a[left_index].isalpha():                                       # left element is a symbol, skip it
            left_index += 1
        elif not a[right_index].isalpha():                                    # right element is a symbol, skip it
            right_index -= 1
        else:
            a[left_index], a[right_index] = a[right_index], a[left_index]     # swap elements at left and right indices
            left_index += 1
            right_index -= 1

    return ''.join(a)

# Try Code
if __name__ == "__main__":
   assert foo('a#') == 'a#'
   assert foo('#a') == '#a'
   assert foo('ab#') == 'ba#'
   assert foo('a#b') == 'b#a'
   assert foo('#ab') == '#ba'
   assert foo('ab,c,de!$') == 'ed,c,ba!$'

---

Files

method1.py
method2.py
method3.py