daily 0.0
知道stoi不能用在string view
把之前75的進度再推一下 好久沒寫==
127. Word Ladder
給beginWord ,endWord
給list [一堆words]
begin一次只能改一個letter
然後一定要變成list裡面的字
算出最少要變幾次才能變成endWord
ㄙ路：
一開始看到list 又只能改一個字
想到之前做拼字錯誤預測==
就建了個小trie
後來發現只拿來check
大家都用hashset QQ
先dfs去找TLE
dp記起來TLE
改BFS
合理多了==
四層 醜死 一堆沒用的判斷式
class Solution {
public:
class trie{
public:
vector<trie*> alp;
bool tail;
trie(){
alp = vector<trie*>(26, nullptr);
tail = false;
}
};
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if(find(wordList.begin(), wordList.end(), endWord) != wordList.end()){
if(beginWord == endWord) return 0;
unordered_map<string, int> step;
step[beginWord] = 1;
vector<bool> dif(10, false);
int len = beginWord.length();
for(int i = 0; i < len; i++){
if(beginWord[i] != endWord[i])
dif[i] = true;
}
trie* root = new trie;
for(string s : wordList){
if(s == beginWord) continue;
trie* t = root;
for(int i = 0; i < len; i++){
if(t->alp[s[i] - 'a'] == nullptr)
t->alp[s[i] - 'a'] = new trie;
t = t->alp[s[i] - 'a'];
}
t->tail = true;
}
//BFS
queue <string> q;
q.push(beginWord);
int d = 1;
while(!q.empty() and step.find(endWord) == step.end()){
queue <string> q2;
while(!q.empty() ){
for(int i = 0; i < len; i++){
for(int j = 0; j < 26; j++){
string s(q.front());
s[i] = (char)('a' + j);
if(endWord == s){
step[s] = d + 1;
return d + 1;
}
if(checkexist(s, root)){
if(step.find(s) == step.end()){
step[s] = d + 1;
q2.push(s);
}
else{
if(step[s] > (d + 1)){
step[s] = d + 1;
q2.push(s);
}
}
}
}
}
q.pop();
}
q = q2;
d++;
}
//dist(step, beginWord, endWord, root, 1);
//dfs TLE
if(step.find(endWord) == step.end()) return 0;
return step[endWord];
}
return 0;
}
bool checkexist(string& s, trie* t){
for(int i = 0; i < s.length(); i++){
if(t->alp[s[i]-'a'] == nullptr) return false;
t = t->alp[s[i]-'a'];
}
return true;
}
/*
void dist(unordered_map<string, int>& step, string cur, string& endWord, trie* root, int d){
// d init = 1
int n = cur.length();
for(int i = 0; i < n; i++){
for(int j = 0; j < 26; j++){
string s(cur);
s[i] = (char)('a' + j);
if(endWord == s){
if(step.find(s) == step.end()){
step[s] = d + 1;
}
else{
step[s] = min(step[s], d + 1);
}
return;
}
if(checkexist(s, root)){
if(step.find(s) == step.end()){
step[s] = d + 1;
dist(step, s, endWord, root, d + 1);
}
else{
if(step[s] > (d + 1)){
step[s] = d + 1;
dist(step, s, endWord, root, d + 1);
}
}
}
}
}
}
*/
/*
void dist(string cur, string& endWord, trie* root, int& res, int d){
cout << cur << " ; \n";
int n = cur.length();
for(int i = 0; i < n; i++){
// cur[i] become *
for(int k = 0; k < 26; k++){
if(k == (int)(cur[i]-'a'))continue;
trie* t = root;
string s;
for(int j = 0; j < n; j++){
//cout << i << " " << j << " " << k << '\n';
if(j == i){
if(t->alp[k] == nullptr) break;
s += (char)('a' + k);
t = t->alp[k];
}
else{
if(t->alp[cur[j]-'a'] == nullptr) break;
s += cur[j];
t = t->alp[cur[j]-'a'];
}
}
if(s == endWord) {
res = min(d + 1, res);
cout << res << " find \n";
//cout << "find\n";
return;
}
else if(s.length() == n){
//delete t; wont be nullptr
t = root;
for(int i = 0; i < n-1; i++){
t = t->alp[s[i]-'a'];
}
t->alp[s[n-1]-'a'] = nullptr;
cout << "nt\n";
dist(s, endWord, root, res, d + 1);
}
}
}
}
*/
};