Блог

Я в замешательстве и не уверен, что делать. Приведенный ниже код — это материал, который я набросал, когда думал о решении.

вот вопрос с примером:

Сообщение, содержащее буквы от A до Z, кодируется в числа с использованием следующего сопоставления:

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26

Учитывая непустую строку, содержащую только цифры, определите общее количество способов ее декодирования.

Пример 1:

Ввод: «12» Вывод: 2 Объяснение: Это может быть декодировано как «AB» (1 2) или «L» (12). Пример 2: Ввод: «226» Вывод: 3 Объяснение: Оно может быть декодировано как «BZ» (2 26), «VF» (22 6) или «BBF» (2 2 6).

 const numDecodings = (s) => {
  // const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')
  // //write an object with alphabets. The numbers will be keys and the letters will be value

  const alphaObject = {
    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'
  };

  const countObj = {};
  // console.log()

  if (s >= "11") {
    s.split("");
    if (!countObj[alphaObject[s]]) {
      return (countObj[alphaObject[s]] = 1);
    }

    //i return the length because
    //i noticed from the examples that the outputs matched the length.
    //since every digit represents a letter.
    //And every letter is a way to do the problem
  } else if (s <= "10") {
    return 1;
  } else if (s === "0") {
    return 0;
  }
  // else if(s.length >= 4){
  //     //test case 1223
  //     //abbc
  //     //lw
  //     //abw
  //     //lbc
  //     //avc
  //     // return s.length   2
  //     s.alphaObject

  // }
};
//getting it wrong for testcase 0
console.log(numDecodings("14"));

  

Это можно сделать рекурсивно:

• Посмотрите, является ли длина строки пустой, чем возвращаемая 1, потому что разделение работает.

• Если это строка, начинающаяся с ‘0’ в первой позиции, то это не может быть никаким решением, потому что (разрешено только 1-26) => возвращает false .

• Если оно имеет длину 1, то это возможно (1-9) => вернуть 1.

• Посмотрите, является ли строка без первого символа возможным решением путем рекурсии, Посмотрите, возможен ли второй метод разделения с 2 цифрами.

• Если строка имеет длину не менее 2 символов, а целочисленное значение не более 26, это может быть решением, продолжайте рекурсивно без первых 2 символов..

• Теперь посмотрите, не являются ли обе попытки ложными => суммируйте оба возвращаемых результата.

• Если только второй не равен false => верните этот результат.

• В противном случае верните первый результат.

 function numDecodings(string) {
    if (string.length===0)
        return 1;
    else if (string.charAt(0)==='0')
        return false;
    else if (string.length==1)
        return 1;
        
    let one = numDecodings(string.slice(1));
          
    let test = parseInt(string.substr(0,2));
    if (string.length>=2 amp;amp; test<=26) {
           let two = numDecodings(string.slice(2));
         if (two!=false amp;amp; one!=false)
             return one two;
         else if (two!=false)
             return two;
    }
    return one;
}

console.log(numDecodings ('226')); // 2,2,6 / 22,6 / 2,26 =>3
console.log(numDecodings ('1223')); // 1,2,2,3 / 12,2,3 / 12,23 / 1,22,3 / 1,2,23 => 5
console.log(numDecodings ('1203')); // 1,20,3 => 1  

Я предлагаю использовать конечные автоматы для моделирования проблемы, как показано выше. Программа запускается в состоянии 0 и анализирует входные данные один символ за другим. Оно может перейти в другое состояние, если будет прочитан символ, показанный на стрелке. Машина может завершить работу только в конечном состоянии, которое равно S0. Теперь мы можем подсчитать количество возможных путей. Пример реализации на JavaScript находится здесь:

 function count(input) {
    return decodingState0(input);
}

function decodingState0(input) {
    if (input.length === 0) {
        return 1;
    }
    const firstNumber = parseInt(input[0]);
    const remaining = input.substring(1);
    let numberPossibilities = 0;
    if (firstNumber > 0) {
        numberPossibilities  = decodingState0(remaining);
    }
    if (firstNumber === 1) {
        numberPossibilities  = decodingState1(remaining);
    } else if (firstNumber === 2) {
        numberPossibilities  = decodingState2(remaining)
    }
    return numberPossibilities;
}


function decodingState1(input) {
    if (input.length === 0) {
        return 0;
    }
    return decodingState0(input.substring(1));
}


function decodingState2(input) {
    if (input.length === 0 || parseInt(input[0]) > 7) {
        return 0;
    }
    return decodingState0(input.substring(1));
}
  

это жесткое требование, согласно которому для связи буквы / слова должны либо иметь разделитель (пробел, запятую и т.д.), Либо должны иметь фиксированный объем пробела (1 символ на букву, 8 бит на символ и т.д.)

без одного из них у вас не будет действительной связи.