5713. 字符串中不同整数的数目

算法

线性扫描

• 线性扫描，用 flag = true 表示当前正在累加数字
• 当遇到一个字母且 flag = true 的时候，表示数字累加完毕，利用 calc 去除前导 0 之后，加入到一个 set 中存储，并且清空当前暂存数字、将 flag 置为 false
• 最终结果就是 set 的大小

C++ 代码

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
    string calc(string t) {
        string u;
        for (int i = 0; i < t.size(); i++) {
            if (t[i] == '0' && u == "") continue;
            u += t[i];
        }
        if (t.size() && u == "") u = "0";
        return u;
    }
    int numDifferentIntegers(string w) {
        unordered_set<string> s;
        bool flag = false;
        string t;
        for (int i = 0; i < w.length(); i++) {
            if (isdigit(w[i]) && !flag) {
                t += w[i];
                flag = true;
            } else if (isdigit(w[i])) {
                t += w[i];
            } else if (!isdigit(w[i])) {
                if (flag) {
                    s.insert(calc(t));
                    t = "";
                }
                flag = false;
            }
        }
        if (flag) {
            s.insert(calc(t));
            t = "";
        }
        return s.size();
    }
};

时间复杂度

• 扫描：O(n)
  • 去除前导 0：O(n)
• 总时间复杂度：O(n^2)