leetcode 1023. Camelcase Matching

博客园 - 司徒正美

leetcode 91. Decode Ways leetcode 1214 Two Sum BSTs leetcode 213 House Robber II leetcode 198 House Robber I leetcode 986. Interval List Intersections leetcode 869. Reordered Power of 2 leetcode 925. Long Pressed Name leetcode 457. Circular Array Loop leetcode 1093. Statistics from a Large Sample leetcode 881. Boats to Save People leetcode 977. Squares of a Sorted Array leetcode 844. Backspace String Compare leetcode 1032. Stream of Characters leetcode 745 Prefix and Suffix Search leetcode 720. Longest Word in Dictionary leetcode 692. Top K Frequent Words leetcode 677. Map Sum Pairs leetcode 676. Implement Magic Dictionary leetcode 648. Replace Words

司徒正美 · 2019-12-30 · via 博客园 - 司徒正美

使用前缀树，多个字符串匹配一个模式

  function Node() {
      this.children = {}
    }
    class Trie {
      constructor() {
        this.root = new Node()
      }
      insert(word) {
        var node = this.root;
        for (let c of word) {
          if (!node.children[c]) {
            node.children[c] = new Node
          }

          node = node.children[c]
        }
        node.word = word;
      }
      search(word) {
        var hash = {}
        innerSearch(this.root, word, 0, true, hash)
        return hash;
      }

    }
    function innerSearch(node, word, index, value, hash) {
      if (node.word) {
        if (index >= word.length) {
          hash[node.word] = value;
        } else {
          hash[node.word] = false
        }
      }

      var a = word[index]
      for (let c in node.children) {
        if (c === a) { //都是大写或小写,并且字母一样
          innerSearch(node.children[c], word, index + 1, value, hash)
        } else {
          var code = c.charCodeAt(0)
          if (code >= 65 && code <= 90) {
            innerSearch(node.children[c], word, index, false, hash)
          } else {
            innerSearch(node.children[c], word, index, value, hash)
          }

        }
      }
      return true
    }

    function camelMatch(queries, pattern) {
      let trie = new Trie
      for (let word of queries) {
        trie.insert(word)
      }
      let hash = trie.search(pattern)
      let ret = []
      for (let word of queries) {
        ret.push(hash[word])
      }

      console.log(ret)
      return ret;
    }
    camelMatch(["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"], 'FB')
    camelMatch(["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"], 'FoBa')
    camelMatch(["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"], 'FBT')

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - 司徒正美