Given a string S, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.
 









Example 1:
Input: "ab-cd"
Output: "dc-ba"


Example 2:
Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"


Example 3:
Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

 

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122 
S doesn't contain \ or "

Source: leetcode | Difficulty: EASY
Tags: String algorithms

Amortized analysis

Starter code: class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        

Solutions:
class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		stack = [char for char in S if char.isalpha()]
		result = ''
		for char in S:
			if char.isalpha():
				temp = stack.pop()
				result += temp
			else:
				result += char
		return result


class Solution:

	def reverseOnlyLetters(self, s: str) -> str:
		a = {}
		j = 0
		s = list(s)
		i = 0
		while i < len(s):
			if not s[i].isalpha():
				a[i + j] = s[i]
				del s[i]
				j += 1
			else:
				i += 1
		s = s[::-1]
		for i in a:
			s.insert(i, a[i])
		return ''.join(s)


class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		if len(S) == 1:
			return S
		start = 0
		end = len(S) - 1
		S = list(S)
		while start < end:
			if S[start].isalpha():
				if S[end].isalpha():
					(S[start], S[end]) = (S[end], S[start])
					start += 1
					end -= 1
				else:
					end -= 1
			else:
				start += 1
		return ''.join(S)


import string

class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		if not S:
			return ''
		stack = []
		deque = collections.deque()
		for (i, c) in enumerate(S):
			if not c.isalpha():
				deque.append((i, c))
			else:
				stack.append(c)
		res = ''
		for i in range(len(S)):
			if deque and i == deque[0][0]:
				res += deque.popleft()[1]
			else:
				res += stack.pop()
		return res


class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		(read_index, write_index) = (len(S) - 1, 0)
		res = list(S)
		while read_index >= 0:
			c = S[read_index]
			if not c.isalpha():
				read_index -= 1
				continue
			while not res[write_index].isalpha():
				write_index += 1
			res[write_index] = c
			read_index -= 1
			write_index += 1
		return ''.join(res)


class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		S = list(S)
		l = 0
		r = len(S) - 1
		while l < r:
			if not S[l].isalpha():
				l += 1
			if not S[r].isalpha():
				r -= 1
			if S[l].isalpha() and S[r].isalpha():
				(S[l], S[r]) = (S[r], S[l])
				l += 1
				r -= 1
		return ''.join(S)


class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		S = list(S)
		start = 0
		end = len(S) - 1
		while start <= end:
			while not S[start].isalpha() and start < end:
				start += 1
			while not S[end].isalpha() and start < end:
				end -= 1
			(S[start], S[end]) = (S[end], S[start])
			start += 1
			end -= 1
		return ''.join(S)


class Solution:

	def reverseOnlyLetters(self, S: str) -> str:
		s = set()
		for i in range(ord('a'), ord('z') + 1):
			s.add(chr(i))
		for i in range(ord('A'), ord('Z') + 1):
			s.add(chr(i))
		order = []
		for i in range(len(S)):
			if S[i] in s:
				order.append(S[i])
		new = []
		order.reverse()
		for i in reversed(S):
			if i in s:
				new.append(order.pop())
			else:
				new.append(i)
		return ''.join(reversed(new))