591.标签验证器.md

591.标签验证器

/*
 * @lc app=leetcode.cn id=591 lang=typescript
 *
 * [591] 标签验证器
 */

// @lc code=start
function isValid(code: string): boolean {}
// @lc code=end

解法 1: 有限状态机

type Node = {
  type: 'TAG_NAME' | 'CDATA'
  content: string
}

type Fn = (char: string) => Fn | null

/**
 * @author XYShaoKang <https://github.com/XYShaoKang>
 */
function isValid(code: string): boolean {
  if (code[0] !== '<') return false
  let root: Node | null = null
  const stack: Node[] = []
  let content = ''
  // 读取字符
  const data: Fn = (char: string) => {
    if (char === '<') {
      // 标签开始字符
      content = ''
      return tagOpen
    }
    content += char
    return data
  }

  // 根据第二个字符判断当前标签类型
  const tagOpen: Fn = (char: string) => {
    if (/[A-Z]/.test(char)) {
      // 第二个字符为大写字母,当前为开始标签
      return tagName(char)
    } else if (char === '/') {
      // 第二个字符为 /,当前为结束标签
      return closeTag
    } else if (char === '!') {
      // 第二个字符为 !,当前标签为 cdata
      return beforeCDATAName
    }
    return null
  }

  const tagName: Fn = (char: string) => {
    if (/[A-Z]/.test(char)) {
      content += char
      return tagName
    }
    if (char === '>') {
      //  检测到标签结束字符 >,检查标签名是否合法
      if (content.length < 1 || content.length > 9) return null
      stack.push({ type: 'TAG_NAME', content })
      content = ''
      return data
    }
    return null
  }
  const closeTag: Fn = (char: string) => {
    if (/[A-Z]/.test(char)) {
      content += char
      return closeTag
    }
    if (char === '>') {
      if (content.length < 1 || content.length > 9) return null

      const node = stack.pop()
      // 检查是否与开始标签一致
      if (node?.type !== 'TAG_NAME' || content !== node.content) return null
      content = ''
      // 如果栈已经被清空,则可以直接返回 end
      if (stack.length === 0) {
        root = node
        return end
      }

      return data
    }
    return null
  }

  const beforeCDATAName: Fn = (char: string) => {
    if (char === '[') return cDATAName
    return null
  }

  const cDATAName: Fn = (char: string) => {
    if (char === '[') {
      // <![ 后面必须跟 CDATA[,否则不合法
      if (content !== 'CDATA') return null

      return cDATAContent(char)
    }
    content += char
    return cDATAName
  }

  const cDATAContent: Fn = (char: string) => {
    if (char === ']') {
      stack.push({ type: 'CDATA', content })
      return beforeCDATAClose
    }
    return cDATAContent
  }
  const beforeCDATAClose: Fn = (char: string) => {
    if (char === ']') {
      content += ']'
      return cDATACloseEnd
    }
    content = stack.pop()?.content + content
    return cDATAContent
  }
  const cDATACloseEnd: Fn = (char: string) => {
    if (char === '>') {
      const node = stack.pop()!
      if (stack.length === 0) {
        root = node
        return end
      }

      return data
    }
    content = stack.pop()?.content + content
    return cDATAContent
  }
  const end: Fn = () => null

  let start: Fn | null = data
  for (let char of code) {
    if (!start) return false
    if (start === end) return false
    start = start(char)
  }

  // 如果是正好闭合的标签,则所有字符访问结束之后
  // start 会等于 end 并且 root 的 type 为 TAG_NAME
  if (start !== end || !root || (root as Node).type !== 'TAG_NAME') return false

  return true
}

Case

test.each([
  { input: { code: '!!!<A>123</A>' }, output: false },
  { input: { code: '<![CDATA[ABC]]><TAG>sometext</TAG>' }, output: false },
  { input: { code: '<A></A>>' }, output: false },
  { input: { code: '<A></A><B></B>' }, output: false },
  { input: { code: '<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>' }, output: false },
  { input: { code: '<DIV>This is the first line <![CDATA[<div>]]></DIV>' }, output: true },
  { input: { code: '<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>' }, output: true },
  { input: { code: '<A>  <B> </A>   </B>' }, output: false },
])('input: code = $input.code', ({ input: { code }, output }) => {
  expect(isValid(code)).toEqual(output)
})