126. Java의 Leetcode 솔루션
3007 단어 java
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
List<List<String>> ans = new ArrayList<>();
if (!words.contains(endWord)) {
return ans;
}
Map<String, List<String>> adjWords = new HashMap<>();
Map<String, Integer> dist = new HashMap<>();
bfs(beginWord, adjWords, dist, words);
dfs(endWord, beginWord, adjWords, dist, new ArrayList<>(), ans);
return ans;
}
public void bfs(String beginWord, Map<String, List<String>> adjWords, Map<String, Integer> dist, Set<String> words) {
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
dist.put(beginWord, 0);
for (String word : words) {
adjWords.put(word, new ArrayList<>());
}
while (!queue.isEmpty()) {
String cur = queue.poll();
List<String> neighbors = neighbors(cur, words);
for (String next : neighbors) {
adjWords.get(next).add(cur);
if (!dist.containsKey(next)) {
dist.put(next, dist.get(cur) + 1);
queue.offer(next);
}
}
}
}
public void dfs(String curWord, String beginWord,Map<String, List<String>> adjWords, Map<String, Integer> dist, List<String> path, List<List<String>> ans) {
path.add(curWord);
if (curWord.equals(beginWord)) {
Collections.reverse(path);
ans.add(new ArrayList<>(path));
Collections.reverse(path);
} else {
for (String next : adjWords.get(curWord)) {
if (dist.containsKey(next) && dist.get(curWord) == dist.get(next) + 1) {
dfs(next, beginWord, adjWords, dist, path, ans);
}
}
}
path.remove(path.size() - 1);
}
public List<String> neighbors(String word, Set<String> words) {
List<String> ans = new ArrayList<>();
char[] sc = word.toCharArray();
for (int i = 0; i < sc.length; i++) {
char cur = sc[i];
for (char c = 'a'; c <= 'z'; c++) {
sc[i] = c;
String temp = new String(sc);
if (words.contains(temp)) {
ans.add(temp);
}
}
sc[i] = cur;
}
return ans;
}
}
리트코드
도전
문제에 대한 링크는 다음과 같습니다.
https://leetcode.com/problems/word-ladder-ii/
Reference
이 문제에 관하여(126. Java의 Leetcode 솔루션), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/chiki1601/126-leetcode-solution-in-java-2b4k
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
문제에 대한 링크는 다음과 같습니다.
https://leetcode.com/problems/word-ladder-ii/
Reference
이 문제에 관하여(126. Java의 Leetcode 솔루션), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/chiki1601/126-leetcode-solution-in-java-2b4k텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)