#1202. Smallest String With Swaps
/// graph
/// using dfs or dfs to solve, 2 array to implement hash table
the hardest problem until now.
string s;
bool comp(int &a, int &b){
return s[a] < s[b];
}
class Solution {
public:
string smallestStringWithSwaps(string inS, vector<vector<int>>& p) {
if( p.size() == 0 ) return inS;
string tmp="------------------------------"; int rrr=0;
s = inS;
for(int k=0; k < 1; k++) {
for(int i=0; i < p.size(); ) { // for all integer list
bool loop_link_found = false;
for(int j=0; j < p.size(); ) { // pick a integer list
if( i==j) { j++; continue;}
bool link_found = false;
for(int n=0; n < p[i].size(); n++) {
for(int m=0; m < p[j].size(); m++) { // for all indices
if( p[i][n] == p[j][m] ) { // check if link was occured
loop_link_found = link_found = true;
break; // break for m, goto break next n
}
}
if( link_found ) break;; // break for n, goto next integer list / j
}
if( link_found ) {
for(int m=0; m < p[j].size(); m++) { // for all indices
if( find(p[i].begin(), p[i].end(), p[j][m]) == p[i].end()) {
p[i].push_back(p[j][m]);
}
}
p.erase(p.begin()+j);
//j=1;
}else j++;
}
if( !loop_link_found ) i++;
}
}
for(int i=0; i < p.size(); i++) {
sort(p[i].begin(), p[i].end(), comp);
}
for(int i=0; i < p.size(); i++) {
for(int j=1; j < p[i].size(); ) {
if( p[i][j] == p[i][j-1]) p[i].erase(p[i].begin()+j);
else j++;
}
}
/*
for(int i=0; i < p.size(); i++) {
for(int j=0; j < p[i].size(); j++)
tmp[rrr++] = p[i][j]+'0';
tmp[rrr++] = '/';
}
*/
// return tmp;
//p[0] = {1,4,5,0,3,3};
string t('.',s.length());
t = s;
for(int i=0; i < p.size(); i++) {
vector<int> new_pair;
new_pair.assign(p[i].begin(), p[i].end());
sort(new_pair.begin(), new_pair.end());
/*
for(int x=0; x < new_pair.size(); x++)
tmp[rrr++] = new_pair[x]+'0';
tmp[rrr++] = '/';
*/
for(int j=0; j < p[i].size(); j++)
t[new_pair[j]] = s[p[i][j]];
}
// return tmp;
return t;
}
};
留言
張貼留言