Bagaimana Mencari Jumlah Kemungkinan dari Pemetaan Angka ke Huruf (1=A - 26=Z) Jika Input Kumpulan Angka?

Dibuat
·
Diperbarui
·
Dilihat90 kali
0

Diketahui 

A = 1 , B = 2 , C = 3 , D = 4, E = 5 , F = 6 dan seterusnya sampai Z = 26

Contoh Soal

Diketahui digit 1232345 , bentuklah kombinasi huruf dari pasangan diatas. 

Jawaban : Jumlah Kombinasi ada 6

[0] => ABCBCDE

[1] => ABCWDE

[2] => AWBCDE

[3] => AWWDE

[4] => LCBCDE

[5] => LCWDE

[0] => 1 2 3 2 3 4 5

[1] => 1 2 3 23 4 5

[2] => 1 23 2 3 4 5

[3] => 1 23 23 4 5

[4] => 12 3 2 3 4 5

[5] => 12 3 23 4 5

catatan : semua digit harus ada

1 2 3 23 tidak valid karena 4 dan 5 tidak ada
3 4 5 tidak valid karena 1 2 3 2 tidak ada

Apabila diketahui digit 1243752521494312

Maka jumlah kombinasi ada berapa ?

Source

function getCombinations(digits) {
  // Mapping digits to letter
  const digitToChar = {
      '1': 'A', '2': 'B', '3': 'C', '4': 'D', '5': 'E', '6': 'F', '7': 'G', '8': 'H', '9': 'I', '10': 'J', '11': 'K', '12': 'L', '13': 'M', '14': 'N', '15': 'O', '16': 'P', '17': 'Q', '18': 'R', '19': 'S', '20': 'T', '21': 'U', '22': 'V', '23': 'W', '24': 'X', '25': 'Y', '26': 'Z'
    };

  // Store valid array
  const combinations = [];

  // Recursion
  function backtrack(start, path) {
    // // When reached the end of the digits, add the combination to the array
    if (start === digits.length) {
      combinations.push(path);
      return;
    }
    // Add letter from 1digit
    const singleDigit = digits[start];
    const singleDigitChar = digitToChar[singleDigit];
    if (singleDigitChar) {
      backtrack(start + 1, path + singleDigitChar);
    }

    // Add letters from two digits if still available
    if (start < digits.length - 1) {
      const twoDigits = digits.slice(start, start + 2);
      const twoDigitsChar = digitToChar[twoDigits];
      if (twoDigitsChar) {
        backtrack(start + 2, path + twoDigitsChar);
      }
    }
  }
  // Invoke recursive function initial value
  backtrack(0, '');
  return combinations;
}
const DIGITS = "1243752521494312";
const combinations = getCombinations(DIGITS);

console.log(`Jumlah Kombinasi ada ${combinations.length}`);
combinations.forEach((combination, index) => {
  console.log(`[${index}] => ${combination}`);
});
JavaScriptAlgoritma
1 Jawaban
1

Mungkin bisa jadi alternatif, tidak menggunakan fungsi rekursif, tapi menggunakan perulangan.

// ...

const digitToChar = Object.fromEntries(
  Array.from({ length: 26 }, (_, i) => [i + 1, String.fromCharCode(65 + i)])
);

function getCombinationsWitoutRecursive(digits) {
  const combinations = [];
  const queues = [[0, ""]];

  while (queues.length > 0) {
    const [start, path] = queues.shift();

    if (start === digits.length) {
      combinations.push(path);
      continue;
    }

    // 1 digit
    const singleDigitChar = digitToChar[digits[start]];
    if (singleDigitChar) {
      queues.push([start + 1, path + singleDigitChar]);
    }

    // 2 digit
    if (start < digits.length - 1) {
      const twoDigitsChar = digitToChar[digits.slice(start, start + 2)];
      if (twoDigitsChar) {
        queues.push([start + 2, path + twoDigitsChar]);
      }
    }
  }

  return combinations;
}

const DIGITS = "1243752521494312";
const DIGITS2 = "1232345";

// getCombinations fungsi original yang pakai rekursif

const expected = getCombinations(DIGITS);
const actual = getCombinationsWitoutRecursive(DIGITS);

const expected2 = getCombinations(DIGITS2);
const actual2 = getCombinationsWitoutRecursive(DIGITS2);

console.log(expected.sort().join("") === actual.sort().join("")); // true
console.log(expected2.sort().join("") === actual2.sort().join("")); // true

console.log(expected.length === actual.length); // true
console.log(expected2.length === actual2.length); // true
Dibuat
·
Diperbarui

Kamu tau jawabannya?

Ayo bergabung bersama lebih dari 200.000 pengguna lainnya!

Pertanyaan Terkait