Сколько слов длины n содержат не более k последовательных гласных?

Question

Сколько слов длины n содержат не более k последовательных гласных?

В нашем алфавите 21 согласная и 5 гласных.

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

Я работаю над этой проблемой с утра, твоя маленькая помощь спасет мне жизнь. Я знаю, что формулировка проблемы расплывчата, но если вы можете намекнуть на этот шаблон программирования Dynami c.

Я обнаружил, что, поскольку это проблема подсчета, мы можем сделать что-то вроде этого dp [i] [j] = длина слова i с j последовательной гласной. Я не знаю, что делать дальше. Пожалуйста, помогите повторить попытку!

Answer 1

Вот решение для программирования c Dynami для того же.

Я использовал массив dp как dp [length_of_string] [2], где

• dp [i ] [0]: общее количество строк длины i с не более чем k последовательных гласных, так что последний символ является гласным
• dp [i] [1]: общее количество строк длины i с не более k последовательные гласные, так что последний символ является согласным

Case 1: i<sup>th</sup> character is consonant

No of choices for consonant, n = 21
dp[i][1] = (n) * (total number of string of length i-1 with at most k consecutive vowels)
dp[i][1] = 21 * (dp[i-1][0] + dp[i-1][1])

Case 2: i<sup>th</sup> character is vowel

if i<sup>th</sup> character is vowel, then it can be preceded by at most k-1 vowels

No of choices for vowels, n = 5

dp[i][0] = (no of strings of length i with at most k consecutive vowels such that last character is a vowel)
              + (no of strings of length i with at most k consecutive vowels such that last 2 characters are vowels) 
              + ... + (no of strings of length i with at most k consecutive vowels such that last k characters are vowels) 

Also, 
no of strings of length i with at most k consecutive
vowels such that last p characters are vowels = (5<sup>p</sup>)*(no of strings of length i-p with at most k consecutive vowels such that last character is a consonant)

So, 
dp[i][0] = (5<sup>1</sup> * dp[i-1][1]) + (5<sup>2</sup> * dp[i-2][1]) + ... + (5<sup>k</sup> * dp[i-k][1])

Наконец,

Ответ будет: Count = dp [length_of_string] [0] + dp [длина_строки] [1]

Реализация в C ++ для logi c выглядит следующим образом:

   #include<bits/stdc++.h>
   #define mod 1000000007
   using namespace std;

   int solve(int wordLen, int maxVowels){
       long long dp[wordLen+1][2];

       dp[0][1] = dp[0][0] = 1;
       dp[1][1] = 21;
       dp[1][0]  = 5;

       for(int i  = 2;i<=wordLen;i++){

           dp[i][1] = (21*(dp[i-1][1]+dp[i-1][0])%mod)%mod;

           int k  = i, j = 1, p = 5;
           dp[i][0] = 0;

           while(k>0 && j<=maxVowels){
               dp[i][0] = (dp[i][0] + (p*dp[i-j][1])%mod)%mod;
               p = (p*5)%mod;
               k--;
               j++;
           } 
       }

       return (int)(dp[wordLen][0]+dp[wordLen][1])%mod;
   }

   int main(){
       cout<<solve(5, 3); 
       return 0;
   }

Answer 2

n = длина. k = максимальное количество последовательных значений. Слово длины i допустимо, если оно имеет не более k последовательных значений.

Пусть f (i, j) = количество допустимых слов длины i, оканчивающихся j гласными.

f(0,0) = 1.
f(i,0) = 21 * (sum from j=0 to min(i-1,k) of f(i-1,j)), for i>0.
f(i,j) = 5*f(i-1, j-1) for 1 <= j <= k.

Решение представляет собой сумму от j = 0 до k из f (n, j).

Это занимает O (k) памяти и O (n * k) времени. Полная таблица - O (nk), но вам нужно только сохранить предыдущую строку на каждом шаге, где строки имеют длину, как в примере ниже.

Пример таблицы для n = 5, k = 2

           0          1          2        

0          1        n/a        n/a
1         21          5        n/a
2        546        105         25
3     14,196      2,730        525
4    366,471     70,980     13,650
5  9,473,121  1,832,355    354,900

Результат: сумма последней строки 11 660 376

Answer 3

Вот рабочая реализация программирования c Dynammi:

#include <iostream>
#include <string.h>
using namespace std;

#define n 5
#define k 2

int arr[n][k + 1];

int fill(int index, int currK){
    if(arr[n][currK] != 0) return arr[n][currK];  //if already calculated
    if(index == n - 1) {                          //base case
        arr[index][currK] = 21 + (currK ? 5 : 0);
        return arr[index][currK];
    }
    
    //recursive condition and step
    if(currK == 0) arr[n][currK] = 21 * fill(index + 1, k);
    else arr[n][currK] = 5 * fill(index + 1, currK - 1) + 21 * fill(index + 1, k);
    return arr[n][currK];   
}

int main(){
    memset(arr, 0, sizeof(arr));
    cout<<fill(0, k)<<endl;

    return 0;
}

Идея состоит в том, чтобы иметь matrix[n][k + 1], где matrix[i][j] хранит возможности для слова размером i, где вы использовали k - j последовательные гласные.

Answer 4

dp[i][j][k] - количество слов длиной i, заканчивающихся буквой j и последними k буквами j

базовый регистр: dp[0][0][1]=1 (проиндексируйте все разрешенные буквы, начинающиеся из 1)

картотека:

dp[i][j][k] = dp[i-1][j][k-1]

if(k == 1)
for j_prev in (0, mxJ):
for k_prev in (1, mxK):
dp[i][j][k]+=dp[i-1][j_prev][k_prev]

Answer 5

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

Этот Python выполняет поиск в онлайн-словаре слов, используя количество символов для определения длины слова и регулярное выражение для n последовательных гласных. Я прочитал описание вашей задачи как означающее именно n последовательных гласных, а не как минимум n.

Python

import re
import urllib


def getwords(length=5, url='http://wiki.puzzlers.org/pub/wordlists/unixdict.txt'):
    "Return lowercased words of given number of characters"
    words = urllib.request.urlopen(url).read().decode().strip().lower().split()
    return (w for w in words if len(w) ==length)

def get_special_words(length=5, consec_vowels=3):
    re_txt = r"[^aeiou\n]*([aeiou]{##CONSEC##})[^aeiou\n]*"
    regex = re.compile(re_txt.replace("##CONSEC##", str(consec_vowels)),
                       re.IGNORECASE | re.VERBOSE | re.DOTALL)
    return (w for w in getwords(length) if regex.search(w))


if __name__ == '__main__':
    wlen, consec = 7, 4
    
    print(f"Dictionary words of length {wlen} with {consec} consecutive vowels:")
    i = 0
    for i, w in enumerate(get_special_words(wlen, consec), 1):
        print(" ", w)
    print(f"\n{i} words found.")

Результат

Dictionary words of length 7 with 4 consecutive vowels:
  aqueous
  sequoia

2 words found.

Ссылка

Регулярное выражение описано .