三刷 05/2022
Version #1 BFS
Time complexity
Each node is visited once by BFS O(n) -> n is #nodes
For each node, find neighbors O(26L^2) ~ O(L^2) -> L is the length of word [new String(chars) takes O(L) time]
Time O(n*L^2)
Space O(n) -> set for all nodes
Runtime: 113 ms, faster than 65.33% of Java online submissions for Word Ladder.
Memory Usage: 82.6 MB, less than 40.89% of Java online submissions for Word Ladder.
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// a.check if two words are adjacent
// Selet two words O(n^2)
// Copare O(wordLen)
// Total: O(wordLen*n^2)
// b.enumerate all possible transformation of each word
// Selet one word O(n)
// Replace each character by 26 characters O(wordLen * 26)
// Check if that transformation is in the wordList O(1) -> use set
// Total: O(26*wordLen*n)
// If wordList is greater than 26, we should use method b
Set<String> wordSet = new HashSet<>(wordList);
// Do breadth first search on the beginWord
Queue<String> que = new ArrayDeque<>();
que.offer(beginWord);
int distance = 1;
while (!que.isEmpty()) {
int size = que.size();
distance++;
while (size-- > 0) {
String curr = que.poll();
for (String neighbor : findNeighbors(curr, wordSet)) {
// System.out.printf("(%s)neighbor(%s)\n", curr, neighbor);
if (neighbor.equals(endWord)) {
return distance;
}
que.offer(neighbor);
}
}
}
return 0;
}
private List<String> findNeighbors(String curr, Set<String> wordSet) {
List<String> neighbors = new ArrayList<>();
char[] chars = curr.toCharArray();
for (int i = 0; i < chars.length; i++) {
char prevChar = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == prevChar) {
continue;
}
chars[i] = c;
String temp = new String(chars);
if (wordSet.contains(temp)) {
neighbors.add(temp);
wordSet.remove(temp);
}
}
chars[i] = prevChar;
}
return neighbors;
}
}
二刷
BFS
Time O(size of wordlist)
Space O(size of wordlist)
71.10 %
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (beginWord == null || endWord == null || wordList == null) return 0;
if (beginWord.equals(endWord)) return 1;
Set<String> visited = new HashSet<>();
Set<String> dict = new HashSet<>();
for (String word : wordList) {
dict.add(word);
}
Queue<String> que = new LinkedList<>();
que.add(beginWord);
visited.add(beginWord);
int step = 0, size;
String currStr;
List<String> neighbors;
while (!que.isEmpty()) {
step++;
size = que.size();
for (int i = 0; i < size; i++) {
currStr = que.poll();
neighbors = getNeighbors(currStr, dict);
for (String neighbor : neighbors) {
if (neighbor.equals(endWord)) return step + 1;
if (visited.contains(neighbor)) continue;
que.offer(neighbor);
visited.add(neighbor);
}
}
}
return 0;
}
//Given a word, return all of its neighbors(have not been visited yet) in the graph as a list
private List<String> getNeighbors(String currStr, Set<String> dict) {
List<String> neighbors = new ArrayList<>();
char[] cArray = currStr.toCharArray();
for (int i = 0; i < currStr.length(); i++) {
//The original character
char temp = cArray[i];
for (char sub = 'a'; sub <= 'z'; sub++) {
if (sub != temp) {
cArray[i] = sub;
String newStr = new String(cArray);
if (dict.contains(newStr)) {
neighbors.add(newStr);
}
}
}
//backtracking
cArray[i] = temp;
}
//System.out.println(neighbors);
return neighbors;
}
}
一刷
public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
public int ladderLength(String start, String end, Set<String> dict) {
// write your code here
int sp = 0;
if (dict == null || dict.size() == 0) {
return sp;
}
if (start.equals(end)) {
return 1;
}
//it is possible that the dict doesn't contain the end word
dict.add(end);
sp = bfs(start, end, dict);
return sp;
}
public int bfs(String start, String end, Set<String> dict) {
int sp = 1;
Queue<String> que = new LinkedList<>();
Set<String> visited = new HashSet<>();
que.offer(start);
visited.add(start);
while(!que.isEmpty()) {
int size = que.size();
sp++;
for (int i = 0; i < size; i++) {
String curr = que.poll();
List<String> neighbors = getNeighbors(curr, dict);
for (String neighbor : neighbors) {
if (neighbor.equals(end)) {
return sp;
}
if (visited.contains(neighbor)) {
continue;
}
if (que.contains(neighbor)) {
continue;
}
que.add(neighbor);
visited.add(neighbor);
}
}
}
return sp;
}
public List<String> getNeighbors(String word, Set<String> dict) {
List<String> neighbors = new ArrayList<>();
for (int k = 0; k < word.length(); k++) {
for (char c = 'a'; c < 'z'; c++ ) {
if (c != word.charAt(k)) {
String newWord = word.substring(0, k) + c + word.substring(k + 1);
if (dict.contains(newWord)) {
neighbors.add(newWord);
}
}
}
}
//System.out.println(neighbors);
return neighbors;
}
}
No comments:
Post a Comment