Fork me on GitHub

Leetcode-FIVE-removeDuplicateLetters

发表于 | 分类于 | 阅读次数:

Remove Duplicate Letters

Description

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example

  1. Example 1:
    Input: “bcabc”
    Output: “abc”

  2. Example 2:
    Input: “cbacdcbc”
    Output: “acdb”

Analysis

这道题要求对于给定输入的字符串，去除重复字母，但是最终结果要求是字典序最小的字符串。从样例来看：

bcabc->abc
重复字母是b和c，可以删去前面的，也可以删去后面的，但是因为a只出现一次，保证字典序最小的话，则需要山区前面的字母b，c使得
结果字符串开头为字母a

这道题巧妙地利用了栈。栈作为先进后出(FILO)的数据结构，可以帮助构造一个严格排序的序列。保证后面入栈的元素，必定比栈顶元素大/小，那么这个栈内元素就是严格排序的。

我们这里求解的是字符串，我们利用一个 string 来模拟栈(c++中，string是一个容器，具有容器通用的增加和删除元素的方法)。我们可以这么考虑：对于字符串中的字符，首先统计其出现次数($O(n)$)，并维护一个数组，统计字符是否已经加入 ans 串。算法过程如下：

从左至右扫描字符：

  1. 该字符出现次数减一；
  2. 对于空的 ans 串，我们直接压入字符；
  3. 若为已经压入 ans 的字符，说明已经排序，可以跳过；
  4. 若为未压入 ans 字符，则和栈顶元素比较，循环执行至其入栈(字符插入合适位置)
    • 循环条件:字符小于栈顶元素&&栈顶元素后续继续出现&&栈非空

这个算法可以保证，每次扫描的字符，可以找到自己的合适位置。

Accept Picture

Accept

Code

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
30
31
32
33
34
35
36
string removeDuplicateLetters(string s) {
  int cnt[26] = {0}, visited[26] = {0};
  for (auto ch : s) cnt[ch - 'a']++;
  
  // Act as a stack
  // Keep the lexicographical order with larger at the top
  string ans;
  
  for (auto ch : s) {
    // char counts decrease
    cnt[ch - 'a']--;

    // ans empty, push char in
    if (ans.empty()) {
      ans.push_back(ch);
      visited[ch - 'a'] = 1;
      continue;
    }

    // if char in ans, continue
    if (visited[ch - 'a'])  continue;

    // if not in ans:
    // if largest in ans no more shows behind, just push
    // else if char smaller than top one, pop until char is largest and push it
    while (ch < ans.back() && !ans.empty() &&
            cnt[ans.back() - 'a'] > 0) {
      visited[ans.back() - 'a'] = 0;
      ans.pop_back();
    }
    ans.push_back(ch);
    visited[ch - 'a'] = 1;
  }
  
  return ans;
}