-
Notifications
You must be signed in to change notification settings - Fork 0
/
minsubstr.cpp
90 lines (81 loc) · 2.11 KB
/
minsubstr.cpp
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//
// minsubstr.cpp
// xcode
//
// Created by Gokul Nadathur on 9/6/16.
// Copyright © 2016 Gokul Nadathur. All rights reserved.
//
#include <string>
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
struct GraphNode {
char label;
int index;
int cost;
GraphNode(char l, int i) : label(l), index(i), cost(-1) {}
void print() {
cout << label << ':' << index << ':' << cost << endl;
}
};
void findMinSeq(vector<GraphNode>& g, char c) {
while (g.size() && g[0].label == c) {
g.erase(g.begin());
}
}
void updatePrev(vector<GraphNode>& g, int index) {
if (g.size() == 1) {
return;
}
auto& e = g[g.size()-2];
e.cost = index - e.index;
}
string minWindow(string s, string t) {
vector<GraphNode> g;
unordered_set<char> tset;
if (s.length() < t.length()) {
return string();
}
if (s.length() == 1) {
return s == t ? s : string();
}
for (auto c : t) {
tset.insert(c);
}
int index = 0;
for (auto c : s) {
if (tset.count(c)) {
g.push_back(GraphNode(c, index));
updatePrev(g, index);
}
index ++;
}
if (g.empty()) {
return string();
}
int end = 0;
bool compacted;
do {
compacted = false;
end = 0;
for (; end < g.size(); ++end) {
if (end > 0 && g[0].label == g[end].label) {
findMinSeq(g, g[end].label);
compacted = true;
}
}
} while (compacted);
return s.substr(g[0].index, g[g.size()-1].index - g[0].index + 1);
}
};
int main(int argc, char** argv) {
//string s = "ADOBECODEBANC", t = "ABC";
string s = "ab", t = "b";
Solution sol;
auto res = sol.minWindow(s, t);
cout << "Result = " << res << endl;
return 0;
}