Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
Given:
start =
"hit"end =
"cog"dict =
["hot","dot","dog","lot","log"]As one shortest transformation is
"hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length
5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
typical BFS and shortest path
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (start == end) return 1;
queue<pair<string,int> > q;
q.push(make_pair(start, 1)); // assign each node a distance
unordered_set<string> used;
while (!q.empty()) {
string top = q.front().first;
int length = q.front().second;
q.pop();
for (int index = 0; index < start.length(); index++ ) {
for (int alp = 'a'; alp < 'z'; alp++) {
if (alp == top[index]) continue; // ignore the same letter
string temp = top;
temp[index] = alp;
if (temp == end) {
return length+1;
}
if (used.find(temp) == used.end() && dict.find(temp) != dict.end()) {
used.insert(temp);
q.push(make_pair(temp, length+1));
}
}
}
}
return 0;
}
};
Java,双向BFS, udpated on Aug-4th-2018
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int len = 1;
Map<String, Boolean> dic = getDic(wordList);
if (!dic.containsKey(endWord)) return 0;
dic.put(beginWord, false);
dic.put(endWord, false);
Set<String> begin = new HashSet<>();
Set<String> end = new HashSet<>();
begin.add(beginWord);
end.add(endWord);
while (!begin.isEmpty() && !end.isEmpty()) {
if (begin.size() > end.size()) {
Set<String> t = begin;
begin = end;
end = t;
}
len++;
Set<String> temp = new HashSet<>();
for (String s : begin) {
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
for (char nextC = 'a'; nextC <= 'z'; nextC++) {
String next = s.substring(0, i) + nextC + s.substring(i + 1);
if (end.contains(next)) return len;
if (dic.containsKey(next) && dic.get(next)) {
temp.add(next);
dic.put(next, false);
}
}
}
}
begin = temp;
}
return 0;
}
private Map<String, Boolean> getDic(List<String> wordList) {
Map<String, Boolean> dic = new HashMap<>();
for (String s : wordList) {
dic.put(s, true);
}
return dic;
}
}
Palindrome PartitioningGiven a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s =
"aab",Return
[
["aa","b"],
["a","a","b"]
]
-----------------------------------------DFS, recursive
class Solution {
public:
bool checkPalin (string s) {
for (int i = 0; i < s.length()/2; i++) {
int end = s.length() - 1 - i;
if (s[i] != s[end]) {
return false;
}
}
return true;
}
void partition (string cur, vector<string> v, string remain, vector<vector<string> >& ret) {
if (remain.empty()) {
ret.push_back(v);
return;
}
for (int i = 0; i < remain.length(); i++) {
cur += remain[i];
if (checkPalin(cur)) {
vector<string> cp = v;
cp.push_back(cur);
partition("",cp,remain.substr(i+1),ret);
}
}
}
vector<vector<string>> partition(string s) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<vector<string> > ret;
vector<string> v;
partition("",v,s,ret);
return ret;
}
};
Update on Oct-03-2014 Using index
class Solution {
public:
bool isPal(string str) {
for (int i = 0; i < str.length() / 2; i++) {
if (str[i] != str[str.length() - 1 - i]) {
return false;
}
}
return true;
}
void dfs(vector<vector<string> > &rt, vector<string> cur, string s,int index) {
if (index == s.length()) {
rt.push_back(cur);
return;
}
for (int i = 1; i < s.length() - index + 1; i++) {
string sub = s.substr(index,i);
if (isPal(sub)) {
vector<string> temp = cur;
temp.push_back(sub);
dfs(rt,temp,s,index + i);
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string> > rt;
vector<string> v;
dfs(rt,v,s,0);
return rt;
}
};
Thoughts: we can add Memoization to improve efficiency. Set up a 2d-array of vector<vector<string>
