301. Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/  b

Solution:
will use BSF strategy. It is like brute force BSF, but will use a hash map to reduce duplicates; and also, this question ask for the minimum change, so once find the valid one, we just need to save all the valid strings in the same "layer" of the BSF.

Code:

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_map<string, int> m;
        queue<string> q;
        q.push(s);
        ++m[s];
        bool found = false;//label for valid layer.
        while(q.size()){
            string t = q.front();
            q.pop();
            if(isValid(t)){
                res.push_back(t);
                found = true;
            }
            if(found) continue;
            for(int i=0; i<t.size(); ++i){
                if(t[i] != '(' && t[i] != ')') continue;
                string temp = t.substr(0, i) + t.substr(i+1);//brute force BSF
                if(m.find(temp) == m.end()){
                    q.push(temp);
                    ++m[temp];
                }
            }
        }
        return res;
    }
private:
    bool isValid(string str){
        int ct = 0;
        for(auto a:str){
            if(a == '(') ++ct;
            if(a == ')' && ct-- == 0) return false;
        }
        return ct == 0;
    }
};

http://www.cnblogs.com/grandyang/p/4944875.html

482. License Key Formatting

https://leetcode.com/contest/leetcode-weekly-contest-14/problems/license-key-formatting/

Solution:
feel like it is not a "medium" level question, should be a "simple" one. Scan from the right to left, if it is '-', remove it; if it is char from 'a' to 'z', convert it to the corresponding uppercase, count + 1; otherwise, count + 1, continue.  If the total elements accumulate to K, add '-'; continue scanning until end.

Code:

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        int i = S.size()-1, t = 0;
        while(i>=0){
            if(S[i] == '-') S.erase(S.begin()+i);
            else{
                if(S[i] >= 'a' && S[i] <= 'z' ) S[i] = S[i] - 'a' + 'A';
                ++t;
                if(t == K){
                    S.insert(S.begin()+i, '-');
                    t = 0;
                }
            }
            --i;
        }
        if(S[0] == '-') S.erase(S.begin());
        return S;
    }
};