Open1
LeetCodeを解く会(TechCommit) 2024
mae616Hard: 127.Word Ladder [Graph, BFS, DFS]
お試しでみんなでHardに挑戦
問題
試行1
アルゴリズム
コード
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
const check = (word, diffword) => {
let count = 0;
for(let i=0; i<word.length; i++){
if(word[i] === diffword[i]) count++;
}
return count === word.length - 1;
}
wordList.sort().reverse();
let min = Infinity;
(function recursion(word, list, count){
if(word === endWord){
min = Math.min(min, count);
return;
}
if(list.length === 0){
return; // 棄却
}
for(let i=list.length - 1; i>=0; i--){
if(check(word, list[i])){
recursion(list[i], list.toSpliced(i, 1), count + 1);
}
}
})(beginWord, wordList.filter(item => item !== beginWord), 1);
return min === Infinity ? 0 : min;
}
結果
Time Limit Exceeded
23 / 51 testcases passed
試行2
アルゴリズム
幅ごとに1つの深さだけ見ていくことにしてみる
コード
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
const check = (word, diffword) => {
let count = 0;
for(let i=0; i<word.length; i++){
if(word[i] === diffword[i]) count++;
}
return count === word.length - 1;
}
const bfs = (word, list) => {
const ary = [];
for(let i=0; i<list.length; i++){
if(check(word, list[i])){
ary.push(list[i]);
}
}
return ary;
};
wordList.sort();
let count = 0;
let candidates = [beginWord];
let exclusions = [[beginWord]]; // 既出
while(candidates.length > 0){
count++;
const nextCandidates = [];
const nextExclusion= [];
for(let i=0; i<candidates.length; i++){
const candidate = candidates[i];
if(candidate === endWord){
return count;
}
const exclusion = exclusions[i];
const list = wordList.filter(item => !exclusion.includes(item));
const ary = bfs(candidates[i], list);
nextCandidates.push(...ary);
nextExclusion.push(...ary.map(item => [...exclusion, item]));
}
candidates = nextCandidates;
exclusions = nextExclusion;
}
return 0;
};
結果
Time Limit Exceeded
25 / 51 testcases passed
また明日考える
試行3
一文字違いを探すごとにO(N)のループしているのが気になる。
ここをうまいデータ構造にできないか？
コード
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
const check = (word, diffword) => {
let count = 0;
for(let i=0; i<word.length; i++){
if(word[i] === diffword[i]) count++;
}
return count === word.length - 1;
}
const wordList2 = [...wordList, beginWord];
const converWordList = {};
for(let i=0; i<wordList2.length; i++){
converWordList[wordList2[i]] = [];
for(let j=0; j<wordList2.length; j++){
if(wordList2[i] === wordList2[j]) continue;
if(check(wordList2[i], wordList2[j])){
converWordList[wordList2[i]].push(wordList2[j]);
}
}
}
let count = 0;
let candidates = [beginWord];
let exclusions = [[beginWord]]; // 既出
while(candidates.length > 0){
count++;
const nextCandidates = [];
const nextExclusion= [];
for(let i=0; i<candidates.length; i++){
const candidate = candidates[i];
if(candidate === endWord){
return count;
}
if(converWordList[candidate].length === 0){
continue;
}
const exclusion = exclusions[i];
const list = converWordList[candidate].filter(item => !exclusion.includes(item));
nextCandidates.push(...list);
nextExclusion.push(...list.map(item => [...exclusion, item]));
}
candidates = nextCandidates;
exclusions = nextExclusion;
}
return 0;0を返します。
};
結果
Time Limit Exceeded
25 / 51 testcases passed
試行4
文字数が小さいから組み合わせみたいにできるか？
コード
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
const check = (word, list) => {
const result = [];
const word2 = word.split('');
const list2 = list.filter(item => item !== word);
for(let i=0; i<word.length; i++){
const reg = new RegExp(word2.toSpliced(i, 1, '.').join(''));
const temp = list2.filter(item => reg.test(item));
if(temp.length > 0){
result.push(...temp);
}
}
return result;
}
const converWordList = {};
converWordList[beginWord] = check(beginWord, wordList);
for(let i=0; i<wordList.length; i++){
converWordList[wordList[i]] = check(wordList[i], wordList);
}
console.log(converWordList)
let count = 0;
let candidates = [beginWord];
let exclusions = [[beginWord]]; // 既出
while(candidates.length > 0){
count++;
const nextCandidates = [];
const nextExclusion= [];
for(let i=0; i<candidates.length; i++){
const candidate = candidates[i];
if(candidate === endWord){
return count;
}
if(converWordList[candidate].length === 0){
continue;
}
const exclusion = exclusions[i];
const list = converWordList[candidate].filter(item => !exclusion.includes(item));
nextCandidates.push(...list);
nextExclusion.push(...list.map(item => [...exclusion, item]));
}
candidates = nextCandidates;
exclusions = nextExclusion;
}
return 0;
};
結果
Time Limit Exceeded
25 / 51 testcases passed
コンソールまでは出てるから、メモ化は終わってるっぽい。探索方法を速くする？
試行5
メモ化でデータと構造ができてるから、startWord → から検索すのと ← endWordから検索するのの両方をやれば、速くなるか？
...考えたけどアルゴリズムが思い浮かばない。
AIによる回答
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function (beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
const getNeighbors = (word) => {
const neighbors = [];
const wordArray = word.split('');
for (let i = 0; i < wordArray.length; i++) {
const originalChar = wordArray[i];
for (let c = 97; c <= 122; c++) { // 'a' to 'z'
const char = String.fromCharCode(c);
if (char === originalChar) continue;
wordArray[i] = char;
const newWord = wordArray.join('');
if (wordSet.has(newWord)) {
neighbors.push(newWord);
}
}
wordArray[i] = originalChar;
}
return neighbors;
};
let beginSet = new Set([beginWord]);
let endSet = new Set([endWord]);
let visited = new Set();
let len = 1;
while (beginSet.size > 0 && endSet.size > 0) {
if (beginSet.size > endSet.size) {
[beginSet, endSet] = [endSet, beginSet];
}
const tempSet = new Set();
for (let word of beginSet) {
const neighbors = getNeighbors(word);
for (let neighbor of neighbors) {
if (endSet.has(neighbor)) {
return len + 1;
}
if (!visited.has(neighbor)) {
visited.add(neighbor);
tempSet.add(neighbor);
}
}
}
beginSet = tempSet;
len++;
}
return 0;
};
双方向BFSていうらしい。今度理解する。