Problem
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"
Solution: Two Pointers
Time complexity: O(n)
Space complexity: O(1) – in place
C++/index
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: string reverseOnlyLetters(string S) { int i = 0; int j = S.length() - 1; while (i < j) { if (isalpha(S[i]) && isalpha(S[j])) { swap(S[i++], S[j--]); } else { if (!isalpha(S[i])) ++i; if (!isalpha(S[j])) --j; } } return S; } }; |
C++/iter
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: string reverseOnlyLetters(string S) { auto it1 = begin(S); auto it2 = prev(end(S)); while (it1 < it2) { if (isalpha(*it1) && isalpha(*it2)) { swap(*it1++, *it2--); } else { if (!isalpha(*it1)) ++it1; if (!isalpha(*it2)) --it2; } } return S; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment