[Day 9] Leetcode 917. Reverse Only Letters (C++)

前言

今天的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.则不需要额外的空间。

结语

不知道发文还能撑几天，最近太忙了，但还是很希望可以藉此来累积一点工作以外的成就>"<
但最近也在想也许取舍很重要，要懂得自己到底想要什麽，不要太贪心什麽都要做。
至少每天花个半小时~一小时写写题目，写写文章，不知道在哪方面会有所收获呢！