子序列

Question

我練面試，碰到這個問題就來了一個網站：

字符串S的神奇的子序列是S子序列 包含所有五個元音順序。查找字符串S中最大的神奇子序列的長度。

例如，如果S = aeeiooua，然後aeiou和aeeioou是神奇的子序列 但aeioaeeioua和不。

我是動態編程的初學者，很難爲此提出一個遞歸公式。

Answer 1

#include <iostream> 
#include<string> 
#include<cstring> 

using namespace std; 
unsigned int getcount(string a, unsigned int l,unsigned int r); 
int main() 
{  
    std::string a("aaaaaeeeeaaaaiiioooeeeeuuuuuuiiiiiaaaaaaoo" 
       "oooeeeeiiioooouuuu"); 
    //std::string a("aaaaaeeeeaaaaiiioooeeeeuuuuuuiiiiiaaaaaaoooooeeeeiiioooo"); 
    //std::string a("aaaaaeeeeaaaaiiioooeeeeiiiiiaaaaaaoooooeeeeiiioooo"); //sol0 
    //std::string a{"aeiou"}; 
    unsigned int len = a.length(); 
    unsigned int i=0,cnt =0,countmax =0; 
    bool newstring = true; 
    while(i<len) 
    { 
     if(a.at(i) == 'a' && newstring == true) 
     { 
      newstring = false; 
      cnt = getcount(a,i,len); 
      if(cnt > countmax) 
      { 
      countmax = cnt; 
      cnt = 0; 
      } 
     } 
     else if(a.at(i)!='a') 
     { 
      newstring = true; 
     } 
     i++; 
    } 
    cout<<countmax; 
    return 0; 
} 

unsigned int getcount(string a, unsigned int l,unsigned int r) 
{ 
    std::string b("aeiou"); 
    unsigned int seq=0,cnt =0; 
    unsigned int current =l; 
    bool compstr = false; 
    while(current<r) 
    { 
     if(a.at(current) == b.at(seq)) 
     { 
      cnt++; 
     } 
     else if((seq <= (b.size()-2)) && (a.at(current) == b.at(seq+1))) 
     { 
      seq++; 
      cnt++; 
      if (seq == 4) 
       compstr =true; 
     } 
     current++; 
    } 
    if (compstr == true) 
     return cnt; 
    return 0; 
} 

Answer 2

，你可以在這裏使用遞歸方法（這應該適用於字符串長度高達最大值INT（容易記憶可以使用）

public class LMV { 

static final int NOT_POSSIBLE = -1000000000; 
// if out put is this i.e soln not possible 


static int longestSubsequence(String s, char[] c) { 

    //exit conditions 
    if(s.length() ==0 || c.length ==0){ 
     return 0; 
    } 

    if(s.length() < c.length){ 
     return NOT_POSSIBLE; 
    } 

    if(s.length() == c.length){ 
     for(int i=0; i<s.length(); i++){ 
      if(s.charAt(i) !=c [i]){ 
       return NOT_POSSIBLE; 
      } 
     } 
     return s.length(); 
    } 

    if(s.charAt(0) < c[0]){ 
     // ignore, go ahead with next item 
     return longestSubsequence(s.substring(1), c); 
    } else if (s.charAt(0) == c[0]){ 
     // <case 1> include item and start search for next item in chars 
     // <case 2> include but search for same item again in chars 
     // <case 3> don't include item 

     return Math.max(
       Math.max( (1+longestSubsequence(s.substring(1), Arrays.copyOfRange(c, 1, c.length))), 
          (1+longestSubsequence(s.substring(1), c))), 
       (longestSubsequence(s.substring(1), c))); 
    } else { 
     //ignore 
     return longestSubsequence(s.substring(1), c); 
    } 
} 



public static void main(String[] args) { 

    char[] chars = {'a', 'e', 'i', 'o', 'u'}; 

    String s1 = "aeio"; 
    String s2 = "aaeeieou"; 
    String s3 = "aaeeeieiioiiouu"; 

    System.out.println(longestSubsequence(s1, chars)); 
    System.out.println(longestSubsequence(s2, chars)); 
    System.out.println(longestSubsequence(s3, chars)); 

} 

}

Answer 3

我有一個迭代的方法做它，而我開始構建類似於LIS（最長增加子序列）的解決方案，然後將其優化到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; 
} 

Answer 4

這是您的問題的Python代碼。 它是否使用非遞歸方法。

從我這裏庫精選：MagicVowels Madaditya

############################################################################ 
# 
# Magical Subsequence of Vowels 
#  by Aditya Kothari (https://github.com/Madaditya/magivvowels) 
# 
# 
############################################################################ 
import sys 
import re 

usage = ''' 
Error : Invalid no of arguments passed. 
Usage : 
python magicv.py string_to_check 
eg: python magicv.py aaeeiiooadasduu 
''' 

def checkMagicVowel(input_string): 
    #The Answer Variable 
    counter = 0 

    #Check if all vowels exist 
    if ('a' in input_string) and ('e' in input_string) and ('i' in input_string) and ('o' in input_string) and ('u' in input_string): 

     vowel_string = 'aeiou' 
     input_string_voweslOnly = '' 

     #Keeping only vowels in the string i.e user string MINUS NON vowels 
     for letter in input_string: 
      if letter in 'aeiou': 
       input_string_voweslOnly = input_string_voweslOnly + letter 

     magic = '' 
     index_on_vowel_string = 0 
     current_vowel = vowel_string[index_on_vowel_string] 
     #i is index on the current Character besing tested 
     i = 0 
     for current_char in input_string_voweslOnly: 

      if current_char == current_vowel: 
       counter = counter + 1 
       magic = magic + current_char 

      if (i < len(input_string_voweslOnly)-1): 
       next_char = input_string_voweslOnly[i+1] 

       if(index_on_vowel_string != 4): 
        next_vowel = vowel_string[index_on_vowel_string+1] 
       else: 
        next_vowel = vowel_string[index_on_vowel_string] 

       #next character should be the next new vowel only to count++ 
       if (current_char != next_char and next_char == next_vowel): 
         if(index_on_vowel_string != 4): 
          index_on_vowel_string = index_on_vowel_string + 1 
         current_vowel = vowel_string[index_on_vowel_string] 

      i = i + 1 
     #Uncomment next line to print the all magic sequences 
     #print magic 

     ''' 
     #Regex Method 
     #magic = re.match('[a]+[e]+[i]+[o]+[u]+',input_string_voweslOnly) 
     magic = re.match('[aeiou]+',input_string_voweslOnly) 
     if magic is not None: 
      ##print magic.group() 
      ##print len(magic.group()) 
     else: 
      ##print(0) 
     ''' 
    else: 
     counter = 0 
    return counter 

if __name__ == "__main__": 

    #checking arguments passed 
    if(len(sys.argv) != 2): 
     print usage 
     sys.exit(0) 
    input_string = sys.argv[1].lower() 

    #get all possible substrings 
    all_a_indices = [i for i, ltr in enumerate(input_string) if ltr == 'a'] 
    substrings = [] 
    for item in all_a_indices: 
     substrings.append(input_string[item:]) 
    #print substrings 

    #Pass each substring and find the longest magic one 
    answer = [] 
    for each in substrings: 
     answer.append(checkMagicVowel(each)) 
    print max(answer)