# 917. Reverse Only Letters
[917. Reverse Only Letters](https://leetcode.com/problems/reverse-only-letters/description/) (<font color="#00AF9B"> Easy</font> 通過率: 66.0%)

## 限制條件
<ul>
<li>1 <= s.length <= 100</li>
<li>s consists of characters with ASCII values in the range [33, 122].</li>
<li>s does not contain '\"' or '\\'.</li>
</ul>

### 解法 1
第一種解法比較土法煉鋼，就是先把倒序的字串存起來，再用一個字串把文字和非文字的字元都排上去

- 時間複雜度: O(n)
- 空間複雜度: O(n)

class Solution {
public:
    string reverseOnlyLetters(string s) {
        vector<int> arr;
        string str;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (!isalpha(s[i])) {
                arr.push_back(i);
            } else {
                str.push_back(s[i]);
            }
        }
        string result;
        for (int s_index = 0, str_index = 0; s_index < s.size(); s_index++) {
            if (find(arr.begin(), arr.end(), s_index) == arr.end()) {
                result.push_back(str[str_index++]);
            } else {
                result.push_back(s[s_index]);
            }
        }
        return result;
    }
};

### 解法 2
第二種是看網路上的，這樣解會快很多，是用 Two Points 的方式，這樣可以省很多空間，不用新增兩串字串浪費記憶體

- 時間複雜度: O(n)
- 空間複雜度: O(1)

class Solution {
public:
    string reverseOnlyLetters(string& s) {
        int size = s.size();
        int left = 0, right = size - 1;
        while (left < right) {
            if (!isalpha(s[left])) {
                left++;
            } else if (!isalpha(s[right])) {
                right--;
            } else {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        return s;
    }
};

</int>