Просмотрите ответ - Decode Ways

Ответ 1

Это действительно интересная проблема. Во-первых, я покажу, как бы я решил эту проблему. Мы увидим, что это не так сложно при использовании рекурсии и что проблема может быть решена с помощью динамического программирования. Мы создадим общее решение, которое не требует жесткого кодирования верхнего предела 26 для каждой кодовой точки.

Заметка о терминологии . Я буду использовать термин "кодовая точка" (CP) не в смысле Unicode, а для обозначения одного из кодовых номеров 1 хотя 26. Каждая кодовая точка представляется как переменное количество символов. Я также буду использовать термины закодированный текст (ET) и чистый текст (CT) в их очевидных значениях. Когда речь идет о последовательности или массиве, первый элемент называется головой. Остальные элементы - это хвост.

Теоретическая прелюдия

• EC "" имеет одно декодирование: CT "".
• EC "3" может быть деструктурирован в '3' + "" и имеет одно декодирование.
• EC "23" может быть деструктурирован как '2' + "3" или '23' + "". Каждый из хвостов имеет одно декодирование, поэтому весь EC имеет два декодирования.
• EC "123" может быть деструктурирован как '1' + "23" или '12' + "3". У хвостов есть два и один декодирования соответственно. Вся EC имеет три декодирования. Деструктурирование '123' + "" неверно, потому что 123 > 26, наш верхний предел.
• ... и т.д. для EC любой длины.

Поэтому, учитывая строку типа "123", мы можем получить количество декодирования, найдя все действующие CP в начале и суммируя количество декодирования каждого хвоста.

Самая сложная часть этого - найти действительные главы. Мы можем получить максимальную длину головы, посмотрев строковое представление верхнего предела. В нашем случае голова может содержать до двух символов. Но не все главы соответствующих длин действительны, потому что они также должны быть ≤ 26.

Наивная рекурсивная реализация

Теперь мы выполнили всю необходимую работу для простой (но работающей) рекурсивной реализации:

static final int upperLimit  = 26;
static final int maxHeadSize = ("" + upperLimit).length();

static int numDecodings(String encodedText) {
    // check base case for the recursion
    if (encodedText.length() == 0) {
        return 1;
    }

    // sum all tails
    int sum = 0;
    for (int headSize = 1; headSize <= maxHeadSize && headSize <= encodedText.length(); headSize++) {
        String head = encodedText.substring(0, headSize);
        String tail = encodedText.substring(headSize);
        if (Integer.parseInt(head) > upperLimit) {
            break;
        }
        sum += numDecodings(tail);
    }

    return sum;
}

Резервированная реализация с кэшем

Очевидно, что это не очень эффективно, потому что (для более длинных ET) один и тот же хвост будет анализироваться несколько раз. Кроме того, мы создаем много временных строк, но мы это пока дадим. Одна вещь, которую мы можем легко сделать, - это мемуаровать количество декодирования определенного хвоста. Для этого мы используем массив той же длины, что и входная строка:

static final int upperLimit  = 26;
static final int maxHeadSize = ("" + upperLimit).length();

static int numDecodings(String encodedText) {
    return numDecodings(encodedText, new Integer[1 + encodedText.length()]);
}

static int numDecodings(String encodedText, Integer[] cache) {
    // check base case for the recursion
    if (encodedText.length() == 0) {
        return 1;
    }

    // check if this tail is already known in the cache
    if (cache[encodedText.length()] != null) {
        return cache[encodedText.length()];
    }

    // cache miss -- sum all tails
    int sum = 0;
    for (int headSize = 1; headSize <= maxHeadSize && headSize <= encodedText.length(); headSize++) {
        String head = encodedText.substring(0, headSize);
        String tail = encodedText.substring(headSize);
        if (Integer.parseInt(head) > upperLimit) {
            break;
        }
        sum += numDecodings(tail, cache);  // pass the cache through
    }

    // update the cache
    cache[encodedText.length()] = sum;
    return sum;
}

Обратите внимание, что мы используем Integer[], а не int[]. Таким образом, мы можем проверить несуществующие записи, используя тест для null. Это решение не только корректно, но и быстро-наивная рекурсия выполняется в O (количество декодирования) времени, а memoized версия работает в O (длина строки).

К DP-решению

Когда вы запускаете над кодом в своей голове, вы заметите, что первый вызов со всей строкой будет иметь промаху в кеше, а затем вычислить количество декодирования для первого хвоста, который также пропускает кеш каждый раз. Мы можем избежать этого, сначала оценив хвосты, начиная с конца ввода. Поскольку все хвосты будут оцениваться до начала всей строки, мы можем удалить проверки на пропуски кеша. Теперь у нас также нет причин для рекурсии, потому что все предыдущие результаты уже находятся в кеше.

static final int upperLimit  = 26;
static final int maxHeadSize = ("" + upperLimit).length();

static int numDecodings(String encodedText) {
    int[] cache = new int[encodedText.length() + 1];

    // base case: the empty string at encodedText.length() is 1:
    cache[encodedText.length()] = 1;

    for (int position = encodedText.length() - 1; position >= 0; position--) {
        // sum directly into the cache
        for (int headSize = 1; headSize <= maxHeadSize && headSize + position <= encodedText.length(); headSize++) {
            String head = encodedText.substring(position, position + headSize);
            if (Integer.parseInt(head) > upperLimit) {
                break;
            }
            cache[position] += cache[position + headSize];
        }
    }

    return cache[0];
}

Этот алгоритм можно было бы оптимизировать, заметив, что мы только запрашиваем последние maxHeadSize элементы в кеше. Поэтому вместо массива мы могли бы использовать очередь фиксированного размера. В этот момент у нас будет динамическое программирующее решение, которое работает в * O (длина входной длины) и O (maxHeadSize).

Специализация для upperLimit = 26

Вышеуказанные алгоритмы были сохранены как можно более общие, но мы можем вручную и вручную их специфицировать для конкретного upperLimit. Это может быть полезно, потому что это позволяет нам делать различные оптимизации. Тем не менее, это вводит "магические числа", которые делают код более сложным для поддержания. Поэтому такие ручные специализации следует избегать в некритичном программном обеспечении (и вышеупомянутый алгоритм уже так же быстро, как и он).

static int numDecodings(String encodedText) {
    // initialize the cache
    int[] cache = {1, 0, 0};

    for (int position = encodedText.length() - 1; position >= 0; position--) {
        // rotate the cache
        cache[2] = cache[1];
        cache[1] = cache[0];
        cache[0] = 0;

        // headSize == 1
        if (position + 0 < encodedText.length()) {
            char c = encodedText.charAt(position + 0);

            // 1 .. 9
            if ('1' <= c && c <= '9') {
                cache[0] += cache[1];
            }
        }

        // headSize == 2
        if (position + 1 < encodedText.length()) {
            char c1 = encodedText.charAt(position + 0);
            char c2 = encodedText.charAt(position + 1);

            // 10 .. 19
            if ('1' == c1) {
                cache[0] += cache[2];
            }
            // 20 .. 26
            else if ('2' == c1 && '0' <= c2 && c2 <= '6') {
                cache[0] += cache[2];
            }
        }
    }

    return cache[0];
}

Сравнение с вашим кодом

Код внешне похож. Тем не менее, ваш синтаксический анализ вокруг символов более запутан. Вы ввели переменную used, которая, если она установлена, уменьшит счетчик декодирования, чтобы учесть двухсимвольные СР. Это неправильно, но я не знаю, почему. Основная проблема заключается в том, что вы удваиваете счет почти на каждом шагу. Как мы видели, предыдущие подсчеты добавляются и могут очень отличаться.

Это означает, что вы написали код без надлежащей подготовки. Вы можете написать много видов программного обеспечения, не думая слишком много, но вы не можете обойтись без тщательного анализа при разработке алгоритма. Для меня часто полезно разрабатывать алгоритм на бумаге и рисовать диаграммы каждого шага (в соответствии с "теоретической прелюдией" этого ответа). Это особенно полезно, когда вы слишком много думаете о языке, который собираетесь внедрить, и слишком мало о возможных ошибках.

Я предлагаю вам прочитать "доказательства по индукции" , чтобы понять, как написать правильный рекурсивный алгоритм. Когда у вас есть рекурсивное решение, вы всегда можете перевести его в итеративную версию.

Ответ 2

Итак, вот какой простой способ решить вашу проблему. Это довольно близко к вычислению Фибоначчи, с той разницей, что есть проверки условий на каждой подзадаче меньшего размера. Сложность пространства O (1), а время O (n)

Код находится в С++.

   int numDecodings(string s)
   {
    if( s.length() == 0 ) return 0;


    int j  = 0;
    int p1 = (s[j] != '0' ? 1 : 0);         // one step prev form j=1
    int p2 = 1;                             // two step prev from j=1, empty
    int p = p1;

    for( int j = 1; j < s.length(); j++ )
    {
        p = 0;

        if( s[j] != '0' ) 
            p += p1;    


        if( isValidTwo(s, j-1, j) )
            p += p2;

        if( p==0 )                  // no further decoding necessary, 
            break;                  // as the prefix 0--j is has no possible decoding.

        p2 = p1;                    // update prev for next j+1;
        p1 = p;

    }

    return p;
    }

    bool isValidTwo(string &s, int i, int j)
    {
        int val= 10*(s[i]-'0')+s[j]-'0';

        if ( val <= 9 ) 
        return false;

        if ( val > 26 ) 
        return false;

        return true;

    }

Ответ 3

Вот мой код для решения проблемы. Я использую DP, я думаю, это понятно.

Написано в Java

public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            int n = s.length();
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = s.charAt(0) != '0' ? 1 : 0;

            for(int i = 2; i <= n; i++){
                int first = Integer.valueOf(s.substring(i-1,i));
                int second = Integer.valueOf(s.substring(i-2,i));
                if(first >= 1 && first <= 9){
                    dp[i] += dp[i-1];
                }
                if(second >= 10 && second <= 26){
                    dp[i] += dp[i-2];
                }

            }
            return dp[n];

        }

}

Ответ 4

Поскольку я сам боролся с этой проблемой, вот мое решение и рассуждения. Вероятно, я в основном повторю то, что написал амон, но, может быть, кто-то найдет его полезным. Также он С# не java.

Скажем, что мы вводим "12131" и хотим получить все возможные декодированные строки. Пряморекурсивное решение будет выполнять итерацию слева направо, получать правильные 1 и 2 цифры головок и вызывать функцию рекурсивно для хвоста.

Мы можем визуализировать его с помощью дерева:

Есть 5 листов, и это число всех возможных расшифрованных строк. Есть также 3 пустых листа, потому что номер 31 не может быть декодирован в букву, поэтому эти листья недействительны.

Алгоритм может выглядеть так:

public IList<string> Decode(string s)
{
    var result = new List<string>();

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                result.Add(this.ToASCII(s));
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                result.Add(this.ToASCII(s.Substring(0, 1)) + this.ToASCII(s.Substring(1, 1)));
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                result.Add(this.ToASCII(s));
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
            {
                var tails = this.Decode(s.Substring(i));
                foreach (var tail in tails)
                    result.Add(this.ToASCII(head) + tail);
            }
        }
    }

    return result;
}

public string ToASCII(string str)
{
    int number = int.Parse(str);
    int asciiChar = number + 65 - 1; // A in ASCII = 65
    return ((char)asciiChar).ToString();
}

Мы должны заботиться о числах, начиная с 0 ( "0", "03" и т.д.) и больше 26.

Потому что в этой задаче нам нужно только подсчитывать способы декодирования, а не фактические строки, мы можем упростить этот код:

public int DecodeCount(string s)
{
    int count = 0;

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                count++;
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                count++;
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                count++;
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
                count += this.DecodeCount(s.Substring(i));
        }
    }

    return count;
}

Проблема с этим алгоритмом заключается в том, что мы вычисляем результаты для одной и той же входной строки несколько раз. Например, есть 3 узла, заканчивающиеся на 31: ABA31, AU31, LA31. Также есть 2 узла, заканчивающиеся на 131: AB131, L131. Мы знаем, что если node заканчивается 31, у него есть только один ребенок, поскольку 31 может быть декодирован только одним способом CA. Аналогично, мы знаем, что если строка заканчивается на 131, она имеет 2 детей, потому что 131 можно декодировать в ACA или LA. Таким образом, вместо того, чтобы сначала вычислять его, мы можем кэшировать его на карте, где ключ - строка (например: "131" ), а значение - количество декодированных способов:

public int DecodeCountCached(string s, Dictionary<string, int> cache)
{
    if (cache.ContainsKey(s))
        return cache[s];

    int count = 0;

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                count++;
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                count++;
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                count++;
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
                count += this.DecodeCountCached(s.Substring(i), cache);
        }
    }

    cache[s] = count;
    return count;
}

Мы можем уточнить это еще дальше. Вместо того, чтобы использовать строки в качестве ключей, мы можем использовать длину, потому что кэширование всегда является хвостом входной строки. Поэтому вместо кеширования строк: "1", "31", "131", "2131", "12131" мы можем кэшировать длины хвостов: 1, 2, 3, 4, 5:

public int DecodeCountDPTopDown(string s, Dictionary<int, int> cache)
{
    if (cache.ContainsKey(s.Length))
        return cache[s.Length];

    int count = 0;

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                count++;
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                count++;
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                count++;
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (s[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
                count += this.DecodeCountDPTopDown(s.Substring(i), cache);
        }
    }

    cache[s.Length] = count;
    return count;
}

Это рекурсивный подход к динамическому программированию сверху вниз. Мы начинаем с самого начала, а затем рекурсивно вычисляем решения для хвостов и запоминаем эти результаты для дальнейшего использования.

Мы можем перевести его на итеративное решение DP снизу вверх. Мы начинаем с конца и результаты кэширования для плиток, как в предыдущем решении. Вместо карты мы можем использовать массив, потому что ключи целые:

public int DecodeCountBottomUp(string s)
{
    int[] chache = new int[s.Length + 1];
    chache[0] = 0; // for empty string;

    for (int i = 1; i <= s.Length; ++i)
    {
        string tail = s.Substring(s.Length - i, i);

        if (tail.Length == 1)
        {
            if (tail[0] != '0')
                chache[i]++;
        }
        else if (tail.Length == 2)
        {
            if (tail[0] != '0' && tail[1] != '0')
                chache[i]++;
            if (tail[0] != '0' && int.Parse(tail) > 0 && int.Parse(tail) <= 26)
                chache[i]++;
        }
        else
        {
            if (tail[0] != '0')
                chache[i] += chache[i - 1];

            if (tail[0] != '0' && int.Parse(tail.Substring(0, 2)) > 0 && int.Parse(tail.Substring(0, 2)) <= 26)
                chache[i] += chache[i - 2];
        }
    }

    return chache.Last();
}

Некоторые люди упрощают его еще дальше, инициализируя кеш [0] со значением 1, поэтому они могут избавиться от условий для tail.Length == 1 и tail.Length == 2. Для меня это неинтуитивный трюк, так как ясно, что для пустой строки существует 0 способов декодирования, а не 1, поэтому в этом случае необходимо добавить дополнительное условие для обработки пустого ввода:

public int DecodeCountBottomUp2(string s)
{
    if (s.Length == 0)
        return 0;

    int[] chache = new int[s.Length + 1];
    chache[0] = 1;
    chache[1] = s.Last() != '0' ? 1 : 0;

    for (int i = 2; i <= s.Length; ++i)
    {
        string tail = s.Substring(s.Length - i, i);

        if (tail[0] != '0')
            chache[i] += chache[i - 1];

        if (tail[0] != '0' && int.Parse(tail.Substring(0, 2)) > 0 && int.Parse(tail.Substring(0, 2)) <= 26)
            chache[i] += chache[i - 2];
    }

    return chache.Last();
}