[伯俊]1759パスワードの作成-javascript

📌 質問する

https://www.acmicpc.net/problem/1759

📌 に答える

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const [L, C] = input.shift().split(' ').map(Number);
const alphabet = input.shift().split(' ').sort();
const vowel = ['a', 'e', 'i', 'o', 'u'];
const answer = [];

function backtracking(str, startIndex) {
  if (str.length === L) {
    let cnt = 0;
    for (let i = 0; i < str.length; i++) {
      if (vowel.includes(str[i])) cnt++;
    }
    if (cnt > 0 && L - cnt > 1) {
      answer.push(str);
    }
    return;
  } else {
    for (let i = startIndex; i < C; i++) {
      backtracking(str + alphabet[i], i + 1);
    }
  }
}

backtracking('', 0);

console.log(answer.join('\n'));

✔アルゴリズム:backtrack+brootforce
✔組合せ問題は、1つ以上の母音、2つ以上の子音を組み合わせた文字列が条件です.
バックグラウンドトラッキングにより文字列を生成します.長さがLの場合、条件判断で条件を満たすと、答えに入ります
✔入力条件ではL、Cの範囲が広くないため、全ての場合閲覧がタイムアウトしない
✔難易度:標準プラチナ5