2020-02-14 刷题 2（字符串）

38 外观数列

简单粗暴，效果也不太好

time: 18.22%, memory: 5.05%
class Solution {
public:
    string countAndSay(int n) {
        string cur_array = "1";
        while(--n){
            string tmp = "";
            char c = cur_array[0];
            int cnt = 1;
            for(int i = 1; i < cur_array.size(); i++){
                if(cur_array[i] == c){
                    cnt++;
                }
                else{
                    tmp = tmp + to_string(cnt);
                    tmp = tmp + c;
                    c = cur_array[i];
                    cnt = 1;
                }
            } 
            tmp = tmp + to_string(cnt);
            tmp = tmp + c;
            cur_array = tmp;
        }
        return cur_array;
    }
};

14 最长公共子前缀

还是最简单的做法，以第一个字符串作为初始前缀，逐个比较得到公共子前缀。做了一步优化，先选出最短的字符串作为初始前缀，然后再比较，能从20ms优化到16ms。如果能先根据字符串长度做一下排序，可能会更快。
代码：

time: 7.31%, memory: 5.02%
class Solution {
public:
    string get_prefix(string s1, string s2){
        int i = 0, j = 0;
        string prefix = "";
        while(i < s1.size() && j < s2.size() && s1[i] == s2[j]){
            prefix = prefix + s1[i];
            i++;
            j++;
        }
        return prefix;
    }
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0) return "";
        int min_len = strs[0].size(), idx = 0;
        for(int i = 1; i < strs.size(); i++){
            if(strs[i].size() < min_len) {
                min_len = strs[i].size();
                idx = i;
            }
        }
        string pre = strs[idx];
        for(int i = 0; i < strs.size(); i++){
            if(i == idx) continue;
            pre = get_prefix(pre, strs[i]);
            if(pre == "") break;
        }
        return pre;
    }
};