我最近正在接受采访，并被问到多个问题，其中一个问题是这个，我在尝试回答它时遇到了一些麻烦。
给定一个字符串，找出出现的最长的元音“aeiou”。元音的子串不必是连续的，并且可以有重复。
目标是找到每个元音的最大出现并加入它们，但它必须是“a”，“e”，“i”，“o”，“u”的顺序。
编辑：此外，每个单独的元音字符也必须链接。在下面的示例中，有“aaa”和“aa”，因为3更长，我们的结果必须包含更长的链。
例如：输入：“aaagtaayuhiejjhgiiiouaae”结果：aaaeiiiou
我尝试过的代码如下：
编辑：在解决方案之后，我在下面写了这个，但我仍然遇到诸如“aeiouaaaeeeiiiooouuu”等字符串的问题。对此的正确结果是15但我得到5。
var findLongestVowels = function(s){
var count = 1;
var i = 0;
var j = 0;
var vowels = ['a','e','i','o','u'];
var total = 0;
var array = [];
while (i < s.length){
if (s.charAt(i) == vowels[j] && s.charAt(i) == s.charAt(i+1) ){
count++;
}
else if (s.charAt(i) == vowels[j] && s.charAt(i) != s.charAt(i+1)){
if (j === 0 && !array[vowels[j]]){
array[vowels[j]] = count;
}
else if (j === 0 && array[vowels[j]]){
array[vowels[j]] = Math.max(array[vowels[j]],count);
}
else if (j !== 0 && !array[vowels[j]] && array[vowels[j-1]]){
array[vowels[j]] = array[vowels[j-1]] + count;
}
else if (j !== 0 && array[vowels[j]] && array[vowels[j-1]]){
array[vowels[j]] = Math.max(array[vowels[j]],array[vowels[j-1]] + count);
}
count = 1;
}
else if (s.charAt(i) == vowels[j+1] && array[vowels[j]]){
j++;
i--;
}
i++;
}
console.log(array);
console.log('Answer: ' + array[vowels[j]]);
}
findLongestVowels("eeeeebbbagtaagaaajaaaaattyuhiejjhgiiiouaae");我至少朝着正确的方向前进吗？
提前致谢。
我们可以在O(n)时间解决这个问题。考虑到对于每个块，如果它的元音位于元音列表中的索引v，我们只对块的最佳解决方案感兴趣，元音顺序为v-1元音。我们为每个块类型（每个元音）保存最后一个最佳解决方案：
|aaa|g|t|aa|y|u|h|i|e|jj|h|g|iii|o|u|aa|e
b: 1 2 3 4 5 6 7 8 9 10
b 1: v[a] = 3
b 2: v[a] = max(2,3)
b 3: v[u] = None recorded for v-1
b 4: v[i] = None recorded for v-1
b 5: v[e] = 1 + 3
b 6: v[i] = 3 + 4
b 7: v[o] = 1 + 7
b 8: v[u] = 1 + 8 // answer
b 9: v[a] = max(2,3)
b 10: v[e] = 1 + 3
JavaScript代码：
function f(str){
console.log(`String: ${ str }\n`);
var vowels = {
a: {best: 0, prev: null},
e: {best: 0, prev: 'a'},
i: {best: 0, prev: 'e'},
o: {best: 0, prev: 'i'},
u: {best: 0, prev: 'o'}
};
function getBlock(i){
let length = 1;
while (str[i+1] && str[i] == str[i+1]){
length++;
i++;
}
return length;
}
for (let i=0; i<str.length;){
let length = getBlock(i);
console.log(`i: ${ i }; length: ${ length }`)
if (!vowels[str[i]]){
i = i + length;
continue;
}
if (!vowels[str[i]].prev){
vowels[str[i]].best = Math.max(
vowels[str[i]].best,
length
);
// make sure the previous vowel
// exists in the string before
// this vowel
} else if (vowels[ vowels[str[i]].prev ].best){
vowels[str[i]].best = Math.max(
vowels[str[i]].best,
length + vowels[ vowels[str[i]].prev ].best
);
}
i = i + length;
}
console.log(`\n${ JSON.stringify(vowels) }\n\n`);
return vowels['u'].best;
}
var s = 'eeeeebbbagtaagaaajaaaaattyuhiejjhgiiiouaae';
console.log(f(s) + '\n\n');
s = 'aaagtaayuhiejjhgiiiouaae';
console.log(f(s) + '\n\n');
s = 'aeiouaaaeeeiiiooouuu';
console.log(f(s));这个问题可以通过使用动态编程技术来解决。
首先，我们有字符串x，我们想找到这个字符串的最长字符串。
从头到尾遍历字符串x，假设在索引i，我们试图找到元音e，有两种可能性：
e，所以我们采取整个块并移动到下一个角色所以，我们有我们的伪代码：
int[][]dp;
int largestBlock (int index, int currentVowel, String x, String vowels){
if (currentVowel == 5) {
// We found all 5 vowel
return 0;
}
if visited this state (index, currentVowel) before {
return dp[index][currentVowel];
}
int result = largestBlock(index + 1, currentVowel, x, vowels) ;
if (x[index] == vowels[currentVowel]){
int nxt = nextIndexThatIsNotVowel(index, currentVowel, x, vowels);
result = max(result, nxt - index + largestBlock(nxt, currentVowel + 1, x , vowels));
}
return dp[index][currentVowel] = result;
}
时间复杂度为O（n * m），m为元音数，在这种情况下为5。
你需要记住单个元音的最大组合。
使用reduce，map和Object.values
var vowels = "aeiou";
var input = "aaagtaayuhiejjhgiiiouaae";
var output = Object.values(
input.split( "" ).reduce( ( a, c, i, arr ) => {
var lastChar = arr[ i - 1 ];
if ( !vowels.includes( c ) ) return a; //if not vowel, return accumulator
if ( c != lastChar ) //if not same as last character then create a new array
{
a[ c ] = a[ c ] || [];
a[ c ].push( [ c ] );
}
else //else push to the last array;
{
var lastCombo = a[ c ].slice( -1 )[ 0 ];
lastCombo.push(c)
}
return a; //return accumulator
} , {}) ).map( s => {
var char = s[0][0]; //find the character to repeat
var maxLength = Math.max.apply( null, s.map( s => s.length ) ); //find how many times to repeat
return Array( maxLength + 1 ).join( char );
}).join( "" ); //join all the vowels
console.log( output );这只是众多可能的解决方案之一 - 随意尝试。
vowels数组中存储您感兴趣的每个元音。map循环遍历数组中的每个元音，从元音创建正则表达式以将字符串拆分为元音数组。例如，“aaabdmedaskaa”将被分成["aaa", "a", "aa"]。0），将出现数组连接到结果字符串。从“a”创建的正则表达式将是undefined，这意味着任何不包含“a”的字符序列。
[^a]+为什么不正则表达式？
function findLongestOccurance(str) {
const vowels = ["a", "e", "i", "o", "u"];
const result = vowels.map(vowel => {
const regex = new RegExp(`[^${vowel}]+`);
return str.split(regex)
.filter(r => r !== "")
.sort((a, b) => b.length - a.length)[0];
});
return result.filter(occ => typeof(occ) !== "undefined").join("");
}
console.log(findLongestOccurance("aaagtaayuhiejjhgiiiouaae"));首先，从我对输入结果的问题的理解：“aaagtaayuhiejjhgiiiouaae”应该是aaaaaeiiiou，就像@PhamTrung在评论中提出但没有得到答案。
因为这是一次面试，我会首先想到的是第一件事，即蛮力解决这个问题
var result = /(a+).*(e+).*(i+).*(o+).*(u+)/.exec("aaagtaayuhiejjhgiiiouaae");
console.log(result[1]+result[2]+result[3]+result[4]+result[5]);这有一个糟糕的运行时间，我们正在尝试所有可能的子串只包含元音，而不是丢弃那些不是所需形式的那些（a + e + i + o + u +）而不是只选择最大的元音商场。如果我没有错，那么Σ（n选择i）的最坏情况是O（n ^ n） - 嗯，这里的实际最坏情况是对于足够大的n的stackOverflow异常，在这种情况下我们有用循环重新实现它而不是递归。在这种情况下，我们仍然可以得到一个内存不足异常，在这种情况下，我们将没有选项，但改进我们的算法。可以想象，如果输入足够大以至于我们得到的内存不足，那么我们的代码也会慢到不能成为问题的合理解决方案。我只是在争论这一切，因为这些是面试官可能希望看到你知道的事情，这意味着你对CS 101有足够的了解。
接下来，面试官会问我是否可以改善表现。这是一个运行时间为O（n）的解决方案。
function a(string, prefix='') {
if(!string.length){
return prefix
}
if(!/[aeiou]/.test(string[0])){
return a(string.substr(1), prefix)
}
const option1 = a(string.substr(1), prefix)
const option2 = a(string.substr(1), prefix+string[0])
const validateRegex = /^a+e+i+o+u+$/
const isValidOption1 = validateRegex.test(option1)
const isValidOption2 = validateRegex.test(option2)
if(isValidOption1 && isValidOption2){
if(option1.length > option2.length) {
return option1
}
return option2
}
if(isValidOption1) {
return option1
}
if(isValidOption2) {
return option2
}
return null
}
const input = 'aaagtaayuhiejjhgiiiouaae'
console.log(a(input))这可以看作是const input = 'aeiouaaaeeeiiiooouuu'
let curr = { "1": {price: -1} }
const nodes = []
const voewels = '1aeiou'
const getPrevLetter = (node) => voewels[voewels.indexOf(node.letter) -1]
let resultNode
function setUpNodeByCurrent(node, letter){
node.price = curr[letter].price + 1
node.previous = curr[letter]
}
function setBestResultIfNeeded(node){
if(node.letter !== 'u') {
return
}
if(!resultNode || resultNode.price < node.price) {
resultNode = node
return
}
}
function setCurrent(letter){
const node = {
letter,
price: 0
}
const prevLetter = getPrevLetter(node)
if(!prevLetter || !curr[prevLetter]){
// either letter isn't on of aeiou or
// we got to an i without ever seeing an e, an o without ever seeing an i, ... this letter is irrelevant
return
}
if(curr[node.letter]) {
setUpNodeByCurrent(node, node.letter)
}
if(node.price < curr[prevLetter].price + 1) {
setUpNodeByCurrent(node, prevLetter)
}
curr[node.letter] = node
setBestResultIfNeeded(node)
}
function getStringResult(node){
let result = ''
while(node) {
result = node.letter + result
node = node.previous
}
return result
}
function getResult(){
const node = resultNode //getBestResultNode()
const result = getStringResult(node)
console.log(result)
console.log(result.length)
}
for(let l of input){
setCurrent(l)
}
getResult()的简化，基本上你会穿过弦，每个longest path problem over a DAG都指向a的下一次出现以及下一次出现的a。 e指向下一个e和下一个e，依此类推。你应该有一个起始节点指向每次出现的每个出现的a和一个末端节点。现在你想要的是从起始节点到结束节点的最长路径，它是一个O（| V | + | E |），现在| V | <= n和| E | <= 2n，因为你的图形中的每个节点最多有2个顶点离开它，因此总运行时间为O（n）。我已经简化了代码来构建结果，因为它继续构建图形，基本上我已经计算了成本，所以当我完成类似于我描述的图形时我已经知道结果是什么。
请注意，此解决方案基于输入字符串必须具有嵌入其中的解决方案的假设。如果输入字符串是无法解析的（其中没有和aeiou序列），则需要正确处理这种情况，添加处理该字符串的代码实际上是微不足道的。在这种情况下，第一个解决方案将返回null（如果我没有记错的话）
希望这可以帮助。