消元法，正则和栈：求解《591. 标签验证器》

消元法

• 通过有限次变换被消除部分元素

Golang 的 regexp 包的常用操作

• 不支持反向引用

package main
import (
 "fmt"
 "regexp"
 "strings"
)
func main() {
 /* 匹配 */
 // regexp.Match + []byte()
 if ok, _ := regexp.Match("[0-9]", []byte("1")); ok {
  fmt.Println("ok")
 }
 // regexp.MatchString
 if ok, _ := regexp.MatchString("[0-9]", "1"); ok {
  fmt.Println("ok")
 }
 /* 解析 */
 // 返回 Regexp 对象指针
 rp, _ := regexp.Compile("[0-9]")

 /* 查找 */
 // 匹配第一个 byte
 first := rp.Find([]byte("abc123"))
 fmt.Println(string(first))

 // 匹配指定个数 byte
 alls := rp.FindAll([]byte("abc123"), 3)
 fmt.Println(alls)

 // 第一次匹配的开始位置和结束位置
 indexs := rp.FindIndex([]byte("abc123abc123"))
 fmt.Println(indexs)

 // 所有匹配的开始位置和结束位置
 indexAlls := rp.FindAllIndex([]byte("abc123abc123"), 2)
 fmt.Println(indexAlls)

 /* 捕获 */
 // 第一次匹配
 rp, _ = regexp.Compile("[a-z]+([0-9]+)[a-z]+(\\d+)")
 group := rp.FindSubmatch([]byte("abc123abc456"))
 fmt.Println(group)
 // 捕获分组 1 - 第一个括号
 fmt.Println(string(group[1]))
 // 捕获分组 2 - 第二个括号
 fmt.Println(string(group[2]))

 // 第一次匹配索引（开始，结束） 捕获分组 1 索引（开始，结束） 捕获分组 2 索引（开始，结束）
 groupIndex := rp.FindSubmatchIndex([]byte("abc123abc456"))
 fmt.Println(groupIndex)

 // 所有匹配
 rp, _ = regexp.Compile("[a-z]+([0-9]+)")
 groupAll := rp.FindAllSubmatch([]byte("abc123abc456"), 2)
 fmt.Println(groupAll)
 // 匹配1
 fmt.Println(string(groupAll[0][0]))
 // 匹配1 捕获1
 fmt.Println(string(groupAll[0][1]))
 // 匹配2
 fmt.Println(string(groupAll[1][0]))
 // 匹配2 捕获1
 fmt.Println(string(groupAll[1][1]))

 // 所有匹配索引（开始 结束） 匹配内捕获分组索引（开始 结束）
 groupAllIndex := rp.FindAllSubmatchIndex([]byte("abc123abc456"), 2)
 fmt.Println(groupAllIndex)

 /* 替换 */
 // 替换 byte
 rp, _ = regexp.Compile("[a-z]")
 rByte := rp.ReplaceAll([]byte("abc123"), []byte("z"))
 fmt.Println(rByte)

 // 替换字符串
 rString := rp.ReplaceAllString("abc123", "z")
 fmt.Println(rString)

 // 替换 byte 函数
 rByteFunc := rp.ReplaceAllFunc([]byte("abc123"), func(a []byte) []byte {
  return []byte(strings.ToUpper(string(a)))
 })
 fmt.Println(string(rByteFunc))

 // 替换字符串函数
 rStringFunc := rp.ReplaceAllStringFunc("abc123", strings.ToUpper)
 fmt.Println(string(rStringFunc))
}

例题

591. 标签验证器

给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：
代码必须被合法的闭合标签包围。否则，代码是无效的。
闭合标签（不一定合法）要严格符合格式：TAG_CONTENT。其中，是起始标签，是结束标签。起始和结束标签中的 TAG_NAME 应当相同。当且仅当 TAG_NAME 和 TAG_CONTENT 都是合法的，闭合标签才是合法的。
合法的 TAG_NAME 仅含有大写字母，长度在范围 [1,9] 之间。否则，该 TAG_NAME 是不合法的。
合法的 TAG_CONTENT 可以包含其他合法的闭合标签，cdata （请参考规则7）和任意字符（注意参考规则1）除了不匹配的<、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则，TAG_CONTENT 是不合法的。
一个起始标签，如果没有具有相同 TAG_NAME 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。
一个<，如果你找不到一个后续的>与之匹配，是不合法的。并且当你找到一个<或</时，所有直到下一个>的前的字符，都应当被解析为 TAG_NAME（不一定合法）。
cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]>之间的字符。
CDATA_CONTENT 可以包含任意字符。cdata 的功能是阻止验证器解析CDATA_CONTENT，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为常规字符。

答案

正则

class Solution {
  function isValid($code) {
    return preg_match('/^(<([A-Z]{1,9})>([^<]*|\g<1>|<!\[CDATA\[([^\]]|\](?!\]>))*\]\]>)*<\/\2>)$/', $code);
  }
}

消元法

var isValid = function(code) {
  if (/^<([A-Z]{1,9})>.*<\/\1>$/.test(code) === false) return false
  code = code.replace(/<!\[CDATA\[.*?\]\]>/g, ' ')
  while (/<([A-Z]{1,9})>[^<]*?<\/\1>/.test(code) === true) {
    code = code.replace(/<([A-Z]{1,9})>[^<]*?<\/\1>/, '')
  }
  return code === ''
};

class Solution {
  function isValid($code) {
    if (preg_match('/^<([A-Z]{1,9})>.*<\/\1>$/', $code) === 0) return false;
    $code = preg_replace('/<!\[CDATA\[.*?\]\]>/', ' ', $code);
    while (preg_match('/<([A-Z]{1,9})>[^<]*?<\/\1>/', $code) === 1) {
      $code = preg_replace('/<([A-Z]{1,9})>[^<]*?<\/\1>/', '', $code);
    }
    return $code === '';
  }
}

栈 · 迭代

var isValid = function(code) {
  if (code.length < 7 || code[0] !== '<') return false 
  const st = [], n = code.length, isUpperCase = (s, i) => s.charCodeAt(i) > 64 && s.charCodeAt(i) < 91
  for (let i = 1; i < n; i++) {
    if (code[i - 1] === '<') {
      if (st[st.length - 1] === 'cdata') continue
      if (code[i] === '!') {
        if (st.length === 0 || code.slice(i + 1, i + 8) !== '[CDATA[') return false
        i += 6
        st.push('cdata')
      } else if(code[i] === '/') {
        if (st.length === 0) return false
        let j = 0     
        while (code[++i] !== '>') if (i >= n || st[st.length - 1][j++] !== code[i]) return false
        if (j !== st[st.length - 1].length || i !== n - 1 && st.length === 1) return false
        st.pop()
      } else if (isUpperCase(code, i)) {
        st.push([code[i]])
        while (code[++i] !== '>') {
          if (i >= n || st[st.length - 1].length === 9 || isUpperCase(code, i) === false) return false
          st[st.length - 1] += code[i]
        }
      } else return false
    } else if (code[i - 1] === ']' && st[st.length - 1] === 'cdata' && code.slice(i, i + 2) === ']>') {
      st.pop()
      i++
    }
  }
  return st.length === 0
};