花花酱 LeetCode 690. Employee Importance

By zxi on September 28, 2017

https://leetcode.com/problems/employee-importance/description/

Problem:

ou are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1

Output: 11

Explanation:

Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3.

So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:

One employee has at most one direct leader and may have several subordinates.
The maximum number of employees won’t exceed 2000.

Idea:

BFS / DFS

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++ / BFS

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

int getImportance(vector<Employee*> employees, int id) {

unordered_map<int, Employee*> es;

for (auto e : employees)

es.emplace(e->id, e);

queue<int> q;

q.push(id);

int sum = 0;

while (!q.empty()) {

int eid = q.front(); q.pop();

auto e = es[eid];

sum += e->importance;

for (auto rid : e->subordinates)

q.push(rid);

}

return sum;

}

};

C++ / DFS

class Solution {

public:

int getImportance(vector<Employee*> employees, int id) {

unordered_map<int, Employee*> es;

for (auto e : employees)

es.emplace(e->id, e);

return dfs(id, es);

}

private:

int dfs(int id, const unordered_map<int, Employee*>& es) {

const auto e = es.at(id);

int sum = e->importance;

for (int rid : e->subordinates)

sum += dfs(rid, es);

return sum;

}

};

花花酱 LeetCode 684. Redundant Connection

By zxi on September 28, 2017

https://leetcode.com/problems/redundant-connection/description/

Problem:

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

Input: [[1,2], [1,3], [2,3]]

Output: [2,3]

Explanation: The given undirected graph will be like this:

/ \

2 - 3

Example 2:

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output: [1,4]

Explanation: The given undirected graph will be like this:

5 - 1 - 2

| |

4 - 3

Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Idea:
DFS / Union-Find

Solutions:

C++ / DFS

// Author: Huahua

// Time Complexity: O(n^2)

// Running Time: 22 ms

class Solution {

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

unordered_map<int, vector<int>> graph;

for (const auto& edge : edges) {

int u = edge[0];

int v = edge[1];

unordered_set<int> visited;

if (hasPath(u, v, graph, visited))

return edge;

graph[u].push_back(v);

graph[v].push_back(u);

}

return {};

}

private:

bool hasPath(int curr,

int goal,

const unordered_map<int, vector<int>>& graph,

unordered_set<int>& visited) {

if (curr == goal) return true;

visited.insert(curr);

if (!graph.count(curr) || !graph.count(goal)) return false;

for (int next : graph.at(curr)) {

if (visited.count(next)) continue;

if (hasPath(next, goal, graph, visited)) return true;

}

return false;

}

};

C++ / Union Find

// Author: Huahua

// Running time: 6 ms

class UnionFindSet {

public:

UnionFindSet(int n) {

ranks_ = vector<int>(n + 1, 0);

parents_ = vector<int>(n + 1, 0);

for (int i = 0; i < parents_.size(); ++i)

parents_[i] = i;

}

// Merge sets that contains u and v.

// Return true if merged, false if u and v are already in one set.

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

// Meger low rank tree into high rank tree

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pv] += 1;

}

return true;

}

// Get the root of u.

int Find(int u) {

// Compress the path during traversal

if (u != parents_[u])

parents_[u] = Find(parents_[u]);

return parents_[u];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

class Solution {

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

UnionFindSet s(edges.size());

for(const auto& edge: edges)

if (!s.Union(edge[0], edge[1]))

return edge;

return {};

}

};

Java / Union Find

// Author: Huahua

// Runtime: 6 ms

class Solution {

class UnionFindSet {

private int[] parents_;

private int[] ranks_;

public UnionFindSet(int n) {

parents_ = new int[n + 1];

ranks_ = new int[n + 1];

for (int i = 0; i < parents_.length; ++i) {

parents_[i] = i;

ranks_[i] = 1;

}

public boolean Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

public int Find(int u) {

while (parents_[u] != u) {

parents_[u] = parents_[parents_[u]];

u = parents_[u];

}

return u;

}

public int[] findRedundantConnection(int[][] edges) {

UnionFindSet s = new UnionFindSet(edges.length);

for (int[] edge : edges)

if (!s.Union(edge[0], edge[1]))

return edge;

return null;

}

Python: Union Find

"""

Author: Huahua

Running Time: 66 ms

"""

class Solution:

def findRedundantConnection(self, edges):

p = [0]*(len(edges) + 1)

s = [1]*(len(edges) + 1)

def find(u):

while p[u] != u:

p[u] = p[p[u]]

u = p[u]

return u

for u, v in edges:

if p[u] == 0: p[u] = u

if p[v] == 0: p[v] = v

pu, pv = find(u), find(v)

if pu == pv: return [u, v]

if s[pv] > s[pu]: u, v = v, u

p[pv] = pu

s[pu] += s[pv]

return []

Python / Union Find V2

"""

Author: Huahua

Runtime: 59 ms (<92.42%)

"""

class UnionFindSet:

def __init__(self, n):

self._parents = [i for i in range(n + 1)]

self._ranks = [1 for i in range(n + 1)]

def find(self, u):

while u != self._parents[u]:

self._parents[u] = self._parents[self._parents[u]]

u = self._parents[u]

return u

def union(self, u, v):

pu, pv = self.find(u), self.find(v)

if pu == pv: return False

if self._ranks[pu] < self._ranks[pv]:

self._parents[pu] = pv

elif self._ranks[pu] > self._ranks[pv]:

self._parents[pv] = pu

else:

self._parents[pv] = pu

self._ranks[pu] += 1

return True

class Solution:

def findRedundantConnection(self, edges):

s = UnionFindSet(len(edges))

for edge in edges:

if not s.union(edge[0], edge[1]): return edge

return None

ndSet(len(edges))

for edge in edges:

if not s.union(edge[0], edge[1]): return edge

return None

花花酱 LeetCode 208. Implement Trie (Prefix Tree)

By zxi on September 27, 2017

Problem:

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Idea:

Tree/children array

Solution:

C++ / Array

// Author: Huahua

// Running time: 99 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

}

p->is_word = true;

}

/** Returns if the word is in the trie. */

bool search(const string& word) const {

const TrieNode* p = find(word);

return p && p->is_word;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

bool startsWith(const string& prefix) const {

return find(prefix) != nullptr;

}

private:

struct TrieNode {

TrieNode():is_word(false), children(26, nullptr){}

~TrieNode() {

for (TrieNode* child : children)

if (child) delete child;

}

bool is_word;

vector<TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

p = p->children[c - 'a'];

if (p == nullptr) break;

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

C++ / hashmap

// Author: Huahua

// Running time: 98 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children.count(c))

p->children[c] = new TrieNode();

p = p->children[c];

}

p->is_word = true;

}

/** Returns if the word is in the trie. */

bool search(const string& word) const {

const TrieNode* p = find(word);

return p && p->is_word;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

bool startsWith(const string& prefix) const {

return find(prefix) != nullptr;

}

private:

struct TrieNode {

TrieNode():is_word(false){}

~TrieNode() {

for (auto& kv : children)

if (kv.second) delete kv.second;

}

bool is_word;

unordered_map<char, TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

if (!p->children.count(c)) return nullptr;

p = p->children.at(c);

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

Java

// Author: Huahua

// Running time: 184 ms

class Trie {

class TrieNode {

public TrieNode() {

children = new TrieNode[26];

is_word = false;

}

public boolean is_word;

public TrieNode[] children;

}

private TrieNode root;

/** Initialize your data structure here. */

public Trie() {

root = new TrieNode();

}

/** Inserts a word into the trie. */

public void insert(String word) {

TrieNode p = root;

for (int i = 0; i < word.length(); i++) {

int index = (int)(word.charAt(i) - 'a');

if (p.children[index] == null)

p.children[index] = new TrieNode();

p = p.children[index];

}

p.is_word = true;

}

/** Returns if the word is in the trie. */

public boolean search(String word) {

TrieNode node = find(word);

return node != null && node.is_word;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

public boolean startsWith(String prefix) {

TrieNode node = find(prefix);

return node != null;

}

private TrieNode find(String prefix) {

TrieNode p = root;

for(int i = 0; i < prefix.length(); i++) {

int index = (int)(prefix.charAt(i) - 'a');

if (p.children[index] == null) return null;

p = p.children[index];

}

return p;

}

Python 1:

"""

Author: Huahua

Running time: 469 ms

"""

class Trie(object):

class TrieNode(object):

def __init__(self):

self.is_word = False

self.children = [None] * 26

def __init__(self):

self.root = Trie.TrieNode()

def insert(self, word):

p = self.root

for c in word:

index = ord(c) - ord('a')

if not p.children[index]:

p.children[index] = Trie.TrieNode()

p = p.children[index]

p.is_word = True

def search(self, word):

node = self.find(word)

return node is not None and node.is_word

def startsWith(self, prefix):

return self.find(prefix) is not None

def find(self, prefix):

p = self.root

for c in prefix:

index = ord(c) - ord('a')

if not p.children[index]: return None

p = p.children[index]

return p

Python 2:

"""

Author: Huahua

Running time: 212 ms

"""

class Trie(object):

def __init__(self):

self.root = {}

def insert(self, word):

p = self.root

for c in word:

if c not in p:

p[c] = {}

p = p[c]

p['#'] = True

def search(self, word):

node = self.find(word)

return node is not None and '#' in node

def startsWith(self, prefix):

return self.find(prefix) is not None

def find(self, prefix):

p = self.root

for c in prefix:

if c not in p: return None

p = p[c]

return p

花花酱 LeetCode 126. Word Ladder II

By zxi on September 26, 2017

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

[

["hit","hot","dot","dog","cog"],

["hit","hot","lot","log","cog"]

]

Note:

Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS to construct the graph + DFS to extract the paths

Solutions:

C++, BFS 1

// Author: Huahua

// Running Time: 216 ms (better than 65.42%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return {};

dict.erase(beginWord);

dict.erase(endWord);

unordered_map<string, int> steps{{beginWord, 1}};

unordered_map<string, vector<string>> parents;

queue<string> q;

q.push(beginWord);

vector<vector<string>> ans;

const int l = beginWord.length();

int step = 0;

bool found = false;

while (!q.empty() && !found) {

++step;

for (int size = q.size(); size > 0; size--) {

const string p = q.front(); q.pop();

string w = p;

for (int i = 0; i < l; i++) {

const char ch = w[i];

for (int j = 'a'; j <= 'z'; j++) {

if (j == ch) continue;

w[i] = j;

if (w == endWord) {

parents[w].push_back(p);

found = true;

} else {

// Not a new word, but another transform

// with the same number of steps

if (steps.count(w) && step < steps.at(w))

parents[w].push_back(p);

}

if (!dict.count(w)) continue;

dict.erase(w);

q.push(w);

steps[w] = steps.at(p) + 1;

parents[w].push_back(p);

}

w[i] = ch;

}

if (found) {

vector<string> curr{endWord};

getPaths(endWord, beginWord, parents, curr, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& beginWord,

const unordered_map<string, vector<string>>& parents,

vector<string>& curr,

vector<vector<string>>& ans) {

if (word == beginWord) {

ans.push_back(vector<string>(curr.rbegin(), curr.rend()));

return;

}

for (const string& p : parents.at(word)) {

curr.push_back(p);

getPaths(p, beginWord, parents, curr, ans);

curr.pop_back();

}

};

C++ / BFS 2

// Author: Huahua

// Running time: 129 ms (better than 80.67%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

vector<vector<string>> ans;

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return ans;

dict.erase(endWord);

const int l = beginWord.length();

unordered_set<string> q{beginWord}, p;

unordered_map<string, vector<string>> children;

bool found = false;

while (!q.empty() && !found) {

for (const string& word : q)

dict.erase(word);

for (const string& word : q) {

string curr = word;

for (int i = 0; i < l; i++) {

char ch = curr[i];

for (int j = 'a'; j <= 'z'; j++) {

curr[i] = j;

if (curr == endWord) {

found = true;

children[word].push_back(curr);

} else if (dict.count(curr) && !found) {

p.insert(curr);

children[word].push_back(curr);

}

curr[i] = ch;

}

std::swap(p, q);

p.clear();

}

if (found) {

vector<string> path{beginWord};

getPaths(beginWord, endWord, children, path, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& endWord,

const unordered_map<string, vector<string>>& children,

vector<string>& path,

vector<vector<string>>& ans) {

if (word == endWord) {

ans.push_back(path);

return;

}

const auto it = children.find(word);

if (it == children.cend()) return;

for (const string& child : it->second) {

path.push_back(child);

getPaths(child, endWord, children, path, ans);

path.pop_back();

}

};

C++ / Bidirectional BFS

// Author: Huahua

// Running time: 39 ms (better than 93.74%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

vector<vector<string>> ans;

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return ans;

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

unordered_map<string, vector<string>> children;

bool found = false;

bool backward = false;

while (!q1.empty() && !q2.empty() && !found) {

// Always expend the smaller queue first

if (q1.size() > q2.size()) {

std::swap(q1, q2);

backward = !backward;

}

for (const string& w : q1)

dict.erase(w);

for (const string& w : q2)

dict.erase(w);

unordered_set<string> q;

for (const string& word : q1) {

string curr = word;

for (int i = 0; i < l; i++) {

char ch = curr[i];

for (int j = 'a'; j <= 'z'; j++) {

curr[i] = j;

const string* parent = &word;

const string* child = &curr;

if (backward)

std::swap(parent, child);

if (q2.count(curr)) {

found = true;

children[*parent].push_back(*child);

} else if (dict.count(curr) && !found) {

q.insert(curr);

children[*parent].push_back(*child);

}

curr[i] = ch;

}

std::swap(q, q1);

}

if (found) {

vector<string> path{beginWord};

getPaths(beginWord, endWord, children, path, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& endWord,

const unordered_map<string, vector<string>>& children,

vector<string>& path,

vector<vector<string>>& ans) {

if (word == endWord) {

ans.push_back(path);

return;

}

const auto it = children.find(word);

if (it == children.cend()) return;

for (const string& child : it->second) {

path.push_back(child);

getPaths(child, endWord, children, path, ans);

path.pop_back();

}

};

花花酱 LeetCode 127. Word Ladder

By zxi on September 25, 2017

https://leetcode.com/problems/word-ladder/description/

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

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.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS

Time Complexity: O(n*26^l) -> O(n*26^l/2), l = len(word), n=|wordList|

Space Complexity: O(n)

Solution 1: BFS

C++

// Author: Huahua

// Running time: 93 ms

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return 0;

queue<string> q;

q.push(beginWord);

int l = beginWord.length();

int step = 0;

while (!q.empty()) {

++step;

for (int size = q.size(); size > 0; size--) {

string w = q.front();

q.pop();

for (int i = 0; i < l; i++) {

char ch = w[i];

for (int j = 'a'; j <= 'z'; j++) {

w[i] = j;

// Found the solution

if (w == endWord) return step + 1;

// Not in dict, skip it

if (!dict.count(w)) continue;

// Remove new word from dict

dict.erase(w);

// Add new word into queue

q.push(w);

}

w[i] = ch;

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 92 ms (<76.61%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Queue<String> q = new ArrayDeque<>();

q.offer(beginWord);

int l = beginWord.length();

int steps = 0;

while (!q.isEmpty()) {

++steps;

for (int s = q.size(); s > 0; --s) {

String w = q.poll();

char[] chs = w.toCharArray();

for (int i = 0; i < l; ++i) {

char ch = chs[i];

for (char c = 'a'; c <= 'z'; ++c) {

if (c == ch) continue;

chs[i] = c;

String t = new String(chs);

if (t.equals(endWord)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.offer(t);

}

chs[i] = ch;

}

return 0;

}

Solution 2: Bidirectional BFS

C++

// Author: Huahua

// Running time: 32 ms (better than 96.6%)

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return 0;

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

int step = 0;

while (!q1.empty() && !q2.empty()) {

++step;

// Always expend the smaller queue first

if (q1.size() > q2.size())

std::swap(q1, q2);

unordered_set<string> q;

for (string w : q1) {

for (int i = 0; i < l; i++) {

char ch = w[i];

for (int j = 'a'; j <= 'z'; j++) {

w[i] = j;

if (q2.count(w)) return step + 1;

if (!dict.count(w)) continue;

dict.erase(w);

q.insert(w);

}

w[i] = ch;

}

std::swap(q, q1);

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 31 ms (<95.17%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Set<String> q1 = new HashSet<>();

Set<String> q2 = new HashSet<>();

q1.add(beginWord);

q2.add(endWord);

int l = beginWord.length();

int steps = 0;

while (!q1.isEmpty() && !q2.isEmpty()) {

++steps;

if (q1.size() > q2.size()) {

Set<String> tmp = q1;

q1 = q2;

q2 = tmp;

}

Set<String> q = new HashSet<>();

for (String w : q1) {

char[] chs = w.toCharArray();

for (int i = 0; i < l; ++i) {

char ch = chs[i];

for (char c = 'a'; c <= 'z'; ++c) {

chs[i] = c;

String t = new String(chs);

if (q2.contains(t)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.add(t);

}

chs[i] = ch;

}

q1 = q;

}

return 0;

}

Python

"""

Author: Huahua

Running time: 115 ms (better than 96.84%)

"""

class Solution(object):

def ladderLength(self, beginWord, endWord, wordList):

wordDict = set(wordList)

if endWord not in wordDict: return 0

l = len(beginWord)

s1 = {beginWord}

s2 = {endWord}

wordDict.remove(endWord)

step = 0

while len(s1) > 0 and len(s2) > 0:

step += 1

if len(s1) > len(s2): s1, s2 = s2, s1

s = set()

for w in s1:

new_words = [

w[:i] + t + w[i+1:] for t in string.ascii_lowercase for i in xrange(l)]

for new_word in new_words:

if new_word in s2: return step + 1

if new_word not in wordDict: continue

wordDict.remove(new_word)

s.add(new_word)

s1 = s

return 0

Huahua's Tech Road

花花酱 LeetCode 690. Employee Importance

花花酱 LeetCode 684. Redundant Connection

花花酱 LeetCode 208. Implement Trie (Prefix Tree)

花花酱 LeetCode 126. Word Ladder II

花花酱 LeetCode 127. Word Ladder

Solution 1: BFS

C++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems