元音的子序列 [英] Sub-sequence of Vowels

问题描述

我正在练习一次面试，并在一个网站上遇到了这个问题：

I was practicing for an interview and came across this question on a website:

一个神奇的字符串子序列 S 是 S 的子序列，其中
依次包含所有五个元音。找到字符串 S 的最大魔术子序列的长度。

A magical sub-sequence of a string S is a sub-sequence of S that contains all five vowels in order. Find the length of largest magical sub-sequence of a string S.

例如，如果 S = aeeiooua ，则 aeiou 和 aeeioou 是神奇的子序列
，但 aeio 和 aeeioua 不是。

For example, if S = aeeiooua, then aeiou and aeeioou are magical sub-sequences but aeio and aeeioua are not.

我是动态编程的初学者，发现很难提出递归公式为了这。

I am a beginner in dynamic programming and am finding it hard to come up with a recursive formula for this.

推荐答案

我是通过迭代方法而不是递归方法来实现的。我开始构建类似于LIS（最长子序列）的解决方案，然后将其优化到O（n）。

I did it with an iterative approach rather than recursive one. I started building solution similar to LIS (Longest Increasing Subsequence) and then optimised it upto O(n).

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string vowel = "aeiou";

int vpos(char c)
{
    for (int i = 0; i < 5; ++i)
        if (c == vowel[i])
            return i;
    return -1;
}

int magical(string s)
{
    int l = s.length();
    int previndex[5] = {-1, -1, -1, -1, -1};    // for each vowel
    vector<int> len (l, 0);
    int i = 0, maxlen = 0;

    // finding first 'a'
    while (s[i] != 'a')
    {
        ++i;
        if (i == l)
            return 0;
    }

    previndex[0] = i;       //prev index of 'a'
    len[i] = 1;

    for ( ++i; i < l; ++i)
    {
        if (vpos(s[i]) >= 0)    // a vowel
        {
            /* Need to append to longest subsequence on its left, only for this vowel (for any vowels) and 
             * its previous vowel (if it is not 'a')
                This important observation makes it O(n) -- differnet from typical LIS
            */
            if (previndex[vpos(s[i])] >= 0)
                len[i] = 1+len[previndex[vpos(s[i])]];

            previndex[vpos(s[i])] = i;

            if (s[i] != 'a')
            {
                if (previndex[vpos(s[i])-1] >= 0)
                    len[i] = max(len[i], 1+len[previndex[vpos(s[i])-1]]);
            }

            maxlen = max(maxlen, len[i]);
        }
    }
    return maxlen;
}

int main()
{
    string s = "aaejkioou";
    cout << magical(s);
    return 0;
}

这篇关于元音的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！