127. 단어 연결 (JS 구현)

1 문제
두 단어 (begin Word 와 endWord) 와 사전 을 지정 하여 begin Word 에서 endWord 로 의 최 단 변환 시퀀스 의 길 이 를 찾 습 니 다.변환 은 다음 과 같은 규칙 을 따라 야 합 니 다. 매번 변환 할 때마다 한 글자 만 바 꿀 수 있 습 니 다.전환 과정 에서 중간 단 어 는 사전 의 단어 여야 합 니 다.설명: 이러한 변환 시퀀스 가 존재 하지 않 으 면 0 으로 돌아 갑 니 다.모든 단 어 는 같은 길 이 를 가지 고 있다.모든 단 어 는 소문 자로 만 이 루어 져 있다.사전 에는 중복 되 는 단어 가 존재 하지 않 습 니 다.begin Word 와 endWord 가 비어 있 지 않 고 다르다 고 가정 할 수 있 습 니 다.예제 1: 입력: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"] 출력: 5 설명: 가장 짧 은 변환 순 서 는 "hit" - > "hot" - > "dot" - > "dog" - > "dog" - > "cog" 입 니 다. 길이 5 를 되 돌려 줍 니 다.예제 2: 입력: beginWord = "hit" endWord = "cog" wordList = ["hot", "dot", "dog", "lot", "log"] 출력: 0 설명: endWord "cog" 는 사전 에 없 기 때문에 변환 할 수 없습니다.
사고
이 문 제 는 그림 의 역 사 를 고찰 하기 시작 했다. 먼저 그림 구 조 를 구축 하고 같은 자 모 를 가 진 단 어 를 연결 하여 allWords, key 는 여러 가지 형식 이다. 예 를 들 어 *ot, value 은 이 형식 을 가 진 단어 목록 이다. 예 를 들 어 hot、dot、lot 이렇게 하면 지 정 된 형식의 단 어 를 신속하게 얻 을 수 있다. 그 다음 에 beginWord 부터 전체 그림 을 광범 위 하 게 옮 겨 다 니 며 찾 을 때endWord 시 전환 경 로 를 얻 었 음 을 나타 낸다.
3 코드

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0;

    let len = beginWord.length;
    const allWords = {};

    for (let word of wordList) {    //      ，   
        for (let i=1; i<=len; i++) {
            let key = `${word.slice(0,i-1)}*${word.slice(i,len)}`;
            if (!allWords[key])  allWords[key] = [];
            allWords[key].push(word);
        }
    }

    const quque = [{word: beginWord, index: 1}];   //index         
    const visited = {};

    while(quque.length > 0) {    //         
        let item = quque.shift();
        for (let i=1; i<=len; i++) {
            let key = `${item.word.slice(0,i-1)}*${item.word.slice(i,len)}`;
            if (!allWords[key]) continue;
            for (let j=0; j<allWords[key].length; j++) {
                let word = allWords[key][j]
                if (word === endWord) return item.index + 1;
                if (visited[word]) continue;
                quque.push({word, index: item.index + 1});
                visited[word] = true;
            }
        }
    }

    return 0;
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

\ # 데이터 구조 와 알고리즘 학습 노트 \ # 검 지 제공 42: 단어 순 서 를 뒤 집기 + 테스트 사례 (자바, C / C +)

2019.1.2 검 지 Offer 는 제로 브러시 개인 노트 정리 (66 문제 전) 디 렉 터 리 전송 문 에서 인터넷 에 서 는 원 서 를 포함 한 많은 방법 이 문장 을 두 번 뒤 집 는 것 이다. 첫 번...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

127. 단어 연결 (JS 구현)

좋은 웹페이지 즐겨찾기