Partition Labels

Dec 06, 2019

第30天,一个月了。

今天的题目是Partition Labels:

这道题的解法如下:

先遍历一次字符串统计字符出现的次数保存在c1上,然后在遍历一次字符串,这次遍历时同样进行统计字符出现次数保存在c2上,并维护一个变量cnum,这个变量cnum表示当前出现过但是未出现完全的字符的种类数。当出现cnum为 0 时,就表示完成了一次划分。代码如下:

vector<int> partitionLabels(string S) {
    vector<int> c1(26, 0);
    for(int i = 0, size = S.size(); i < size; i++) {
        c1[S[i] - 'a']++;
    }
    
    vector<int> c2(26, 0);
    vector<int> res;
    int temp = 1, cnum = 0;
    
    for(int i = 0, size = S.size(); i < size; i++, temp++) {
        int index = S[i] - 'a';
        if (c2[index] == 0) {
            cnum++;
        }
        if (++c2[index]== c1[index] && --cnum == 0) {
            res.push_back(temp); temp = 0;
        }
    }
    return res;
}
LeetCodeLeetCode

Longest Word in Dictionary through Deleting

Add and Search Word - Data structure design

comments powered by Disqus