javascript - javascript中基于大小写字母的字符串匹配

Question

我今天在 JavaScript 的技术面试中被问到这个问题，我失败了，但我仍然找不到解决方案。我想出的问题和解决方案如下。我实现了通过一些测试用例，但代码仍然无法在所有情况下工作。如果有人帮助我以有效的方式解决它，我将不胜感激。

---

给你一个字符串，输入，由不同大小写的字母组成。

这些字母应该根据大小写相互配对。例如，字母“N”与字母“a”按此顺序形成“匹配对”。

规则:

1. 第一个字母必须大写。
2. 每个大写字母后面都必须跟有它的小写版本或任何大写字母。
3. 当大写字母后跟小写字母时，这两个字母被视为“匹配对，然后可以忽略不计，不再考虑进一步的匹配。”
4. 如果这些规则中的任何一个被打破，或者遇到一个小写字母没有与其最近的未匹配的左邻居创建“匹配对”，则该字母和所有后续字母都被视为“不匹配”。

输出:您的方法应返回最后一个匹配小写字母的从零开始的索引，如果不存在对，则返回 -1。

限制:0 < input length < 10,000 characters 最优方法的运行时间为 O(input length)。

示例输入 #1

ABba

示例输出 #1

3

这就是我所做的，但它并不适用于所有测试用例；

function stringMatch(str){

  let word=str.split("")
  let lastIndex;

  if (word[0]===word[0].toUpperCase()){
    for(let i=0;i<word.length;i++){
      if(word[i]===word[i].toUpperCase()){
        if(word[i].toLowerCase()===word[i+1] || word[i+1]===word[i+1].toUpperCase() ){
          lastIndex=i
        }
        else{
          return -1
        }
      }
      else{
        lastIndex=i
      }

    }
    return lastIndex
  }

}

Answer 1

一个很好的方法是使用一个包含大写字母的堆栈。堆栈的下一个元素应该始终是您要匹配的下一个小写字母。

循环遍历字符串，对于每个字母，如果是大写字母，则将其压入堆栈并继续。如果是小写，则从堆栈中弹出一个并进行比较。如果它们匹配，则将索引设置为最后匹配的并继续，如果它们不匹配，则返回最后匹配的索引。

const isUpper = (l) => l === l.toUpperCase()

function findUnmatchedIndex(str)  {
    let stack = []
    let lastMatch = -1
    for (let i = 0; i < str.length; i++) {
        let letter = str[i]
        if (isUpper(letter)) {
            stack.push(letter);
            continue;
        }
        let next = stack.pop()
        if (next !== letter.toUpperCase()) return lastMatch
        lastMatch = i
    }
    return lastMatch

}

console.log(findUnmatchedIndex('ABba'))
console.log(findUnmatchedIndex('ABCcDEedFeGHi'))
console.log(findUnmatchedIndex('ABCbDEedFeGHi'))