长度为 n 的单词最多有 k 个连续元音？

问题描述 投票：0回答：6

有多少个长度为 n 的单词最多有 k 个连续元音？

我们的字母表有 21 个辅音和 5 个元音。

请原谅我没有提供测试用例。我没有测试用例，因为这是给朋友的电话面试问题。

我从早上就开始解决这个问题，你的一点帮助救了我的命。 我知道问题陈述很模糊，但如果您可以提供有关此动态编程模式的一些提示。

我发现，由于它是计数问题，我们可以这样做 dp[i][j] = length of word i with j肤连续元音。 我不知道如何继续。请帮助重现！

algorithm dynamic-programming permutation combinatorics
6个回答
3
投票

这是一个有效的动态规划实现：

#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
连续元音。

1
投票

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]
1
投票

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.

解决方案是 f(n,j) 从 j = 0 到 k 的和。

这需要 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

1
投票

这是一个相同的动态规划解决方案。

我使用 dp 数组作为 dp[ length_of_string ][ 2 ]，其中

  • dp[ i ][ 0 ] ：长度为 i 且最多有 k 个连续元音的字符串总数，使得最后一个字符是元音
  • dp[ i ][ 1 ] ：长度为 i 且最多有 k 个连续元音且最后一个字符为辅音的字符串总数
情况 1：第 ith 字符是辅音

辅音的选择数量，n = 21
dp[i][1] = (n) * (长度为 i-1 且最多有 k 个连续元音的字符串总数)
dp[i][1] = 21 * (dp[i-1][0] + dp[i-1][1])

情况 2：第 ith 字符是元音

如果第 ith 字符是元音，那么它前面最多可以有 k-1 个元音

元音没有选择，n = 5

dp[i][0] =（长度为 i 且最多有 k 个连续元音且最后一个字符是元音的字符串的数量）
              +（长度为 i 且最多有 k 个连续元音的字符串的数量，使得最后 2 个字符是元音）
              + ... +（长度为 i 的字符串中最多有 k 个连续元音，使得最后 k 个字符是元音）

还，
长度为 i 且最多连续 k 个的字符串的数量
最后 p 个字符是元音的元音 = (5p)*（长度为 i-p 且最多有 k 个连续元音的字符串的数量，使得最后一个字符是辅音）

所以，
dp[i][0] = (51 * dp[i-1][1]) + (52 * dp[i-2][1]) + ... + (5k  * dp[i-k][1])

最后，

答案是，Count = dp[ length_of_string ][ 0 ] + dp[ length_of_string ][ 1 ]

该逻辑的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;
   }
0
投票

可以使用正则表达式来解决该问题。如果你能提供一个适当的解决方案，你可能必须坚持正确性胜过迂腐。

此 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.

参考。

正则表达式描述。

0
投票

这是一个自下而上方法的 C++ DP 解决方案

  • n
    = 字符串长度
  • m
    = 允许的连续元音的最大数量
  • dp[i][j]
    表示长度为 
    i
    且连续具有 
    j
    元音作为后缀的不同字符串的数量。
    vector<vector<int>> dp(n+1, vector<int>(m+1,0));
    dp[0][0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=m; j>=0; j--){
            // transition from dp[i-1][j] to dp[i][j+1] or dp[i][0]
            if(j == m){
                // we cannot add another vowel
                dp[i][0] += 21*dp[i-1][j];
            }
            else{
                dp[i][0] += 21*dp[i-1][j];
                dp[i][j+1] += 5*dp[i-1][j];
            }
        }
    }
    int ans = 0;
    for(int i=0; i<=m; i++){
        ans += dp[n][i];
    }
    cout<<ans<<endl;
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.