Word Ladder

📌 문제

• 시작단어와 끝 단어가 주어진다. ex) 시작 : hit // 끝 : cog
• 중간단어들이 주어진다. ex) ["hot","dot","dog","lot","log","cog"]
• 단어들은 한 글자씩 바뀔 수 있다. ex) hit -> hot
• 바뀐 단어가 중간 단어에 포함돼 있다면, 그 단어는 해당 단어로 바뀔 수 있다.
• 시작단어에서 시작해서 중간 단어들을 걸쳐서 끝 단어로 갈 때, 몇 단계를 거치는 지 출력하라.

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

📌 문제 풀이

• 해당 단어를 맨 앞자리 부터 맨 뒷자리까지 알파벳 26자리를 전부 넣으면서 바꿔본다.
• 해당 단어가 중간 단어에 해당한다면, queue에 넣는다.
• queue에는 처음 시작 값을 넣고, queue가 빌때까지 돌린다.
• end 단어가 나온다면 멈춘다.

🔥 문제

• time limit exceeded 가 생긴다. 다른 풀이로 풀어야 될 것 같긴하다.

📌 배운점

🔥 1. set remove

if(set.contains( 지울 것 ) ) {
set.remove(지울 것)
}

=

if(set.remove(지울 것))

🔥 2. char ch

static String alphas = "abcdefghijklmnopqrstuvwxyz";
static char[] alphaChars;

alphaChars = alphas.toCharArray();
for(int i=0;i<26;i++) {...}

=

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

🔥 3. Arrays.asList

String[] words = {"hot","dog","lot","log","cog"};
List<String> wordList = Arrays.asList(words);

🔥 4. string s = new String(Character 배열)

chars[i] = alphaChars[j];
String s = new String(chars);

📌 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"hot","dog","lot","log","cog"};
        List<String> wordList = Arrays.asList(words);

        int i = solution.ladderLength("hit", "cog", wordList);
        System.out.println(i);
    }
    static class Solution {

        static String alphas = "abcdefghijklmnopqrstuvwxyz";
        static char[] alphaChars;

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            alphaChars = alphas.toCharArray();

            Set<String> set = new HashSet<>(wordList);
            set.add(endWord);

            Queue<String> queue = new LinkedList<>();
            queue.offer(beginWord);

            int level=1;

            while(!queue.isEmpty()){
                int size = queue.size();
                while( size -- > 0){
                    String poll = queue.poll();
                    if(poll.equals(endWord)) return level;

                    for(String s : getNeighbors(poll,wordList)){
                        queue.offer(s);
                    }
                }
                level++;
            }
            return level;
        }
        List<String> getNeighbors(String poll , List<String> wordList){
            Set<String> set= new HashSet<>(wordList);

            List<String> res= new ArrayList<>();

            /*
            for(char ch='a';ch<'z';ch++){
            System.out.println(ch);
            }
             */

            for(int i=0;i<poll.length();i++){
                char[] chars = poll.toCharArray();
                for(int j=0;j<26;j++){
                    chars[i] = alphaChars[j];
                    String s = new String(chars);

                    // set.contains + set.remove
                    if(set.remove(s)){
                        res.add(s);
                    }
                }
            }
            return res;
        }
    }
}