代码之家 › 专栏 › 技术社区 › Ugur Yilmaz

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

string javascript

Ugur Yilmaz · 技术社区 · 8 年前

在今天的JavaScript技术面试中,有人问我这个问题,我失败了,但我仍然无法找到解决方案。我提出的问题和解决办法如下。我实现了通过一些测试用例,但代码仍然不能在所有情况下都工作。如果有人能帮我解决这个问题,我会很感激的。

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

规则:

第一个字母必须大写。
当一个大写字母后跟小写字母时,这两个字母被视为“匹配对”,在进一步的匹配考虑中可以忽略不计。
如果这些规则中的任何一个被破坏,或者遇到一个小写字母,而这个字母没有与其最近的未匹配的左邻居创建一个“匹配对”,则该字母和后面的所有字母都被视为“未匹配”。

限制: 0 < input length < 10,000

样本输入#1

ABba

样本输出#1

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
  }

}

2 回复 | 直到 8 年前

Mark 8 年前

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

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

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'))

Scott Sauyet 8 年前

如果没有更多的测试用例,我不确定这一点。但这看起来可能符合要求。

const isLower = (c) => 'a' <= c && c <= 'z'
const final = (stack) => stack[stack.length - 1]
const initial = (stack) => stack.slice(0, stack.length - 1)

const check = (str) => str.split('').reduce(
  ({lastIndex, failed, stack}, c, idx) => 
    failed
    ? {lastIndex, failed, stack}  // one reason not to do this with reduce.
    : isLower(c)
      ? c === final(stack)
        ? {lastIndex: idx, failed, stack: initial(stack)}  
        : {lastIndex, failed: true, stack}
      : {lastIndex, failed, stack: stack.concat(c.toLowerCase())},
  {lastIndex: -1, failed: false, stack: []}
).lastIndex


console.log(check('ABba'))