前言

今天的daily challenge題目是917. Reverse Only Letters，是easy的題目，不過可以應用到stack的概念！我們一起來看看吧！

想法

看到這題目當下有兩種作法想法:

1. 用stack來存：先遍歷過一次，把所有的英文字母存入stack中，再遍歷一次，把stack裡面的東西pop出來，結束！
2. 頭尾掃描：同時從頭、跟從尾出發，直到兩個都遇到英文字母為止，然後使用swap進行交換

在此之前，要判斷一個字元是否為英文字，除了可以暴力的使用-'a'跟-'A'來看是否位於0~25之間(隱含轉換的用法可以參考Day 3提過的內容，這幾天也都有用到)，也可以使用isalpha()這個函式。
我們直接來看看以上兩種做法分別怎麼做呢~

1. stack版本

class Solution {
public:
    string reverseOnlyLetters(string s) {
        // if english char, save to stack
        stack<int> st;
        for(int i=0;i<s.length();++i){
            if(isalpha(s[i])){
                st.push(s[i]);
            }
        }
        // iterate again
        string ans;
        for(int i=0;i<s.length();++i){
            if(isalpha(s[i])){
                ans+=st.top();
                st.pop();
            }else{
                ans+=s[i];
            }
        }
        return ans;
    }
};

2. 頭尾掃描

class Solution {
public:
    string reverseOnlyLetters(string s) {
        // 2 pointers
        int l = 0;
        int r = s.length() - 1;
        
        while(l<r){
            while(l<s.length() && !isalpha(s[l])){
                ++l;
            }
            while(r>=0 && !isalpha(s[r] )){
                --r;
            }
            if(l>=r){
                break;
            }
            swap(s[l],s[r]);
            ++l;
            --r;
        }
        return s;
    }
};

以上兩個時間複雜度都是O(n)，不過1.要掃兩次，2.只要掃一次
另外空間複雜度，1.需要O(k)的空間來存，2.則不需要額外的空間。

結語

不知道發文還能撐幾天，最近太忙了，但還是很希望可以藉此來累積一點工作以外的成就>"<
但最近也在想也許取捨很重要，要懂得自己到底想要什麼，不要太貪心什麼都要做。
至少每天花個半小時~一小時寫寫題目，寫寫文章，不知道在哪方面會有所收穫呢！