完成度最高的周赛了，主要是这周的周赛题目偏水~ 正常应该是会卡一题。刚开始的时候被同事拉去对接口了，导致时间没有把握住。正常开赛的时候应该就超时了。
这次还有一个区别是，首次尝试直接在面板上code。不使用编译器调试，感觉快了很多。
屏幕快照 2018-11-19 下午7.14.20.png
前三题就不说了，水题~
Valid Mountain Array
直接枚举最高点，遍历验证即可
Delete Columns to Make Sorted
直接遍历行，发现是非法数据累加即可。 Medium通过率比Easy还高，难度标签不太准确~
DI String Match
简单贪心，每次I插入当前最小值，每次D插入当前最大值
Delete Columns to Make Sorted
这题展开讲一下：
题目大意：给定一个字符串列表，求一个最小字符串。使列表中所有的字符串都是它的子串
注意数据规模：
1 <= A.length <= 12
1 <= A[i].length <= 20
这里因为数据规模较小，我直接采用暴力广度优先搜索。
以string - index 状态表示当前搜索状态，index为 (1<<A.length)-1最终状态，表示A列表中所有字符串都为当前string的子串。
注意每加入一个字符串，先查找一下是否是当前子串。再进行首尾合并，优先压入合并最短的字符串。
因为广度优先搜索，先到最终状态的string未必是最优解。所以我一开始等队列全部出完(感觉应该不会超时)。。。结果TL了。
后面，将队列改为优先队列 就过了。
class Solution {
public:
string mergeAB(const string a,const string b){
if(a.length() < 1) return b;
if(b.length() < 1) return a;
string ab = a + b;
string mn = a;
string mx = b;
for(auto npos = mn.length(); npos > 0 ; --npos){
if(npos <= mx.length() && mn.substr(mn.length() - npos, npos) == mx.substr(0, npos)){
ab = mn + mx.substr(npos, mx.length() - npos);
break;
}
}
return ab;
}
string mergeStr(const string a, const string b){
if(a.find(b) != string::npos) return a;
if(b.find(a) != string::npos) return b;
string ab = mergeAB(a,b);
string ba = mergeAB(b,a);
return ab.length() < ba.length() ? ab : ba;
}
string shortestSuperstring(vector<string>& A) {
typedef pair<string, int> state;
int n = A.size();
auto cmp = [](const state a,const state b){
return a.first.length() > b.first.length();
};
priority_queue<state, vector<state>, decltype(cmp)> Q(cmp);
vector<int> vis(1<<n, INT_MAX);
string ans;
for(auto i=0;i<A.size();++i){
Q.push(make_pair(A[i], 1<<i));
vis[1<<i] = true;
ans += A[i];
}
while(!Q.empty()){
state now = Q.top();
Q.pop();
if(now.second == (1<<n) -1) {
return now.first;
}
for(int i=0;i<A.size();++i){
state nxt = now;
nxt.second = now.second | (1<<i);
nxt.first = mergeStr(now.first, A[i]);
if(nxt.first.length() < vis[nxt.second]){
vis[nxt.second] = nxt.first.length();
Q.push(nxt);
}
}
}
return ans;
}
};
