2273. Find Resultant Array After Removing Anagrams

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> ret;
        ret.push_back(words[0]);
        int n = words.size();
        string last = words[0];
        sort(last.begin(), last.end());
        for(int i=1;i<n ;++i) {
            string w = words[i];
            sort(w.begin(), w.end());
            if(last == w) continue;
            else {
                ret.push_back(words[i]);
                last = w;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    
    vector<string> removeAnagrams(vector<string>& words) {
        int n =words.size();
        stack<int> sta({0});
        vector<string> ret;
        for(int i=1;i<n;++i){
            string temp = words[i];
            sort(temp.begin(), temp.end());
            if(!sta.empty()){
                string a = words[sta.top()];
                sort(a.begin(), a.end());
                if(a==temp) continue;
                else{
                    sta.push(i);
                }
            }
        }
        while(!sta.empty()){
            int i = sta.top();
            ret.push_back(words[i]);
            sta.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
        
    }
};

analysis

  • time complexity O(n*mlogm)
  • space complexity O(n)