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.
Given a string, only reverse the letters and keep other characters in the same place. For example, reverseOnlyLetters(“ab-cde”) returns “ed-cba”.
Two Pointers Approach in C++
Let’s use two pointers at two ends – move towards each other to the middle until they meet, ignoring non-letters via !isalpha – and swap two letters at each iteration. The in-place swapping implementation is O(N) time and O(1) space:
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: string reverseOnlyLetters(string S) { int len = static_cast<int>(S.size()); int i = 0, j = len - 1; while (i < j) { while ((i < j) && (!isalpha(S[i]))) i ++; while ((i < j) && (!isalpha(S[j]))) j --; swap(S[i ++], S[j --]); } return S; } }; |
class Solution {
public:
string reverseOnlyLetters(string S) {
int len = static_cast<int>(S.size());
int i = 0, j = len - 1;
while (i < j) {
while ((i < j) && (!isalpha(S[i]))) i ++;
while ((i < j) && (!isalpha(S[j]))) j --;
swap(S[i ++], S[j --]);
}
return S;
}
};We can also do this using additional string copy O(N) space.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: string reverseOnlyLetters(string S) { auto len = S.size(); string r = S; int i = 0, j = len - 1; while (i < j) { while ((i < j) && (!isalpha(S[i]))) i ++; while ((i < j) && (!isalpha(S[j]))) j --; swap(r[i ++], r[j --]); } return r; } }; |
class Solution {
public:
string reverseOnlyLetters(string S) {
auto len = S.size();
string r = S;
int i = 0, j = len - 1;
while (i < j) {
while ((i < j) && (!isalpha(S[i]))) i ++;
while ((i < j) && (!isalpha(S[j]))) j --;
swap(r[i ++], r[j --]);
}
return r;
}
};In Java, we can convert the string to CharArray and then swap the two elements in the array, finally convert the charArray to string using String.valueOf. Please be noted that the String in Java are immutable so that you can’t simply swap/modify the characters in a Java string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public String reverseOnlyLetters(String S) { int i = 0, j = S.length() - 1; char[] r = S.toCharArray(); while (i < j) { while (i < j && !Character.isLetter(S.charAt(i))) ++i; while (i < j && !Character.isLetter(S.charAt(j))) --j; char t = r[i]; r[i] = r[j]; r[j] = t; i ++; j --; } return String.valueOf(r); } } |
class Solution {
public String reverseOnlyLetters(String S) {
int i = 0, j = S.length() - 1;
char[] r = S.toCharArray();
while (i < j) {
while (i < j && !Character.isLetter(S.charAt(i))) ++i;
while (i < j && !Character.isLetter(S.charAt(j))) --j;
char t = r[i];
r[i] = r[j];
r[j] = t;
i ++;
j --;
}
return String.valueOf(r);
}
}See also: Teaching Kids Programming – Reverse Only Letters via Two Pointer Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Pipeline the Functions in C++?
Next Post: Binary Search Algorithm in Java
