const auto new_states = state_extend_function(word,dict,visited,end);
unordered_set<string>::iterator itv;
for ( itv=new_states.begin();itv != new_states.end();itv++ ){
string state=*itv;// state
}
an error:
Solution. H :72:15: error: no match for ‘operator=’ (operand types are ‘STD)
Does not match on both ends of the
the equals sign, may be auto version of c + + 11 different reasons. Change the following to pass:
unordered_set<string> new_states = state_extend_function(word,dict,visited,end);
. The complete code of the original and revised version is as follows:…
Given two words (start and end) and a dictionary, find all the shortest transformation sequences from start to end
For example:
-
- can only change one letter at a time.
- intermediate words in the transformation must appear in the dictionary.
Matters needing attention
1. All words have the same length.
2. All words contain only lowercase letters.
The sample
The data are as follows:
Start = “hit”
End = “cog”
Dict = [” hot “, “dot”, “dog” and “lot”, “log”]
return
[
[” hit “, “hot”, “dot”, “dog”, “cog”].
[” hit “, “hot” and “lot”, “log”, “cog”]
]
Idea: BFS.
#include <iostream>
#include <vector>
#include <limits.h>
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
void gen_path(unordered_map<string, vector<string> > &father,
vector<string> &path, const string &start, const string &word,
vector<vector<string> > &result) {
path.push_back(word);
if (word == start) {
result.push_back(path);
reverse(result.back().begin(), result.back().end());
} else {
vector<string> ::iterator itfv;// for (const auto& f : father[word]) {
for (itfv = (father[word]).begin();itfv !=(father[word]).end();itfv++ ) {
auto f=*itfv;
gen_path(father, path, start, f, result);
}
}
path.pop_back();
}
unordered_set<string> state_extend_function(const string &s,
const unordered_set<string> &dict, unordered_set<string> visited,string end) {
unordered_set<string> result;
for (size_t i = 0; i < s.size(); ++i) {
string new_word(s);
for (char c = 'a'; c <= 'z'; c++) {
if (c == new_word[i]) continue;
swap(c, new_word[i]);
if ((dict.count(new_word) > 0 || string(new_word) == string(end) ) &&
!visited.count(new_word)) {
result.insert(new_word);
}
swap(c, new_word[i]); //
}
}
return result;
}
vector<vector<string> > findLadders(string start, string end,
const unordered_set<string> &dict) {
unordered_set<string> current, next; //
unordered_set<string> visited; //
unordered_map<string, vector<string> > father; // Tree
bool found = false;
auto state_is_target = [&](const string &s) {
return s == end;
};
current.insert(start);
while (!current.empty() && !found) {
// Make all of this layer accessible to prevent the same layer from pointing to each other for(const auto& word:current)
unordered_set<string>::iterator it;
for ( it=current.begin();it != current.end();it++ ){
string word=*it;
visited.insert(word);
}
unordered_set<string>::iterator itc;
for ( itc=current.begin();itc != current.end();itc++ ){
string word=*itc;
unordered_set<string> new_states = state_extend_function(word,dict,visited,end);
unordered_set<string>::iterator itv;
for ( itv=new_states.begin();itv != new_states.end();itv++ ){
string state=*itv;
if (state_is_target(state)) found = true;
next.insert(state);
father[state].push_back(word);
// visited.insert(state);
}
}
current.clear();
swap(current, next);
}
vector<vector<string> > result;
if (found) {
vector<string> path;
gen_path(father, path, start, end, result);
}
return result;
}
void main(){
string start="hit",end="cog";
string sArr[]={"hot","dot","dog","lot","log"};
int len=sizeof(sArr)/sizeof(sArr[0] );
unordered_set<string> dict( sArr ,sArr+len);
findLadders(start, end,dict);
cout<<"out="<<endl;
system("pause");
}
.
Many high-level languages have introduced the concept of lambda expressions, or anonymous functions.
.
Read More:
- error: src refspec master does not match any [How to Solve]
- C++ Primer Program in VsCode error: no match for call to ‘(std::__cxx11::string…)
- error: src refspec master does not match any. [How to Solve]
- error: src refspec master does not match any [How to Solve]
- [Solved] Error: SRC refspec master doors not match any
- [Solved] MindSpore Error: ValueError: Minimum inputs size 0 does not match…
- Oracle prompt text does not match format string
- [Solved] error LNK2038: Detected mismatch of “RuntimeLibrary”: The value “MDd_DynamicDebug” does not match the value “MTd_StaticDebug”
- [Solved] Eureka Startup Error: Root name (‘timestamp‘) does not match expected type EurekaApplications
- [Solved] Canal Error: CanalParseException: column size is not match,parse row data failed
- [Solved] QT cmak Compile Error: CMake Error: The source.. does not match the soused
- [Solved] Camera Calibration Error: ErrorMessage: Image size does not match the measurement in camera parameters
- [How to Solve] Content with element type ‘mapper’ must match
- [Solved] Git Common Error: error: src refspec xxx does not match any/error: failed to push some refs to
- [Solved] Tensorflow/Keras Error reading weights: ValueError: axes don‘t match array
- [Solved] kitt2bag Error: Failed to find match for field intensity
- [Solved] Postcss Error: Invalid options object. PostCSS Loader has been initialized using an options object that does not match the API schema.
- Failed to transform file ‘xxx‘ to match attributes [How to Solve]
- [Solved] Android Error: E/EGL_adreno: tid 3927: eglSurfaceAttrib(1334): error 0x3009 (EGL_BAD_MATCH)
- [Solved] MindSpore Error: StridedSlice operator does not support input of uint8 data type on Ascend hardware