字符串专题

[RubyLouvre]

3. Longest Substring Without Repeating Characters

   Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

也是使用滑动窗口

 var lengthOfLongestSubstring = function (str) {

 if (!str) {
          return 0
        }
        var map = new Array(128 - 32).fill(0) //空字符串为32
        function getIndex(s, i) {
          return s.charCodeAt(i) - 32
        }
        var len = str.length, max = 0
        var left = 0, right = 0
        while (left < len) {
          var index = getIndex(str, right)
          if (map[index] === 0 && right < len) {
            map[index]++
            right++
          } else {
            if (right - left > max) {
              max = right - left
            }
            index = getIndex(str, left)
            map[index]--
            left++
          }
        }
        return max
}

[RubyLouvre]

KMP

//保存的是前缀的起始位置，因此又叫前缀数组，
//又因为它只在失配时才使用，因此又叫失配数组
function getMaxLength(pattern) {
  var table = [0],////只有一个字符肯定不匹配
    i = 1,//最大后缀字符串从1开始 
    j = 0,//前缀的指针
    pLen = pattern.length
  while (i < pLen) {
    if (pattern[i] == pattern[j]) {
      table[i] = j + 1;
      j++;
      i++;
    } else {
      table[i] = 0;
      if (j === 0) {          
        i++;
      } else {
        j = table[j - 1];
      }

    }
  }
  return table;
}

    function getMaxLength2(pattern) {
      var len = pattern.length;
      var PMT = [0]
      var i = 1;
      var k = 0;
      while (i < len) {
        if (pattern[i] == pattern[k]) {
          // 如果是连续的，那么k+1
          k++;
          PMT[i] = k;
          i++;
        } else {
          if (k != 0) {
            k = PMT[k - 1];
          } else {
            PMT[i] = 0;
            i++;
          }
        }
      }

      return PMT;
    }
    function getMaxLength3(pattern) {
      var len = pattern.length;
      var table = [0]
      var i = 1;
      var j = 0;
      while (i < len) {
        if (pattern[i] == pattern[j]) {

          table[i] = j + 1;
          j++
          i++;
        } else {
          table[i] = 0;
          if (j == 0) {

            i++;
          } else {
            j = table[j - 1];
          }
        }
      }

      return table;
    }

    function indexOf(target, pattern) {
      var pmt = getMaxLength(pattern)
      var i = 0, j = 0;
      var tLen = target.length;
      var pLen = pattern.length;
      while (i < tLen && j < pLen) {
        // console.log("i, j ",i, j , target[i] , pattern[j])
        if (target[i] == pattern[j]) {
          i++;
          j++;

        } else {
          if (j == 0) {
            i++; //如果是target[0] !== pattern[0], 那么i还是需要移动
          } else {
            j = pmt[j - 1];// i不动，j从pmt中取
          }
        }
      }
      return j === pLen ? i - j : -1
    }

    function test(a, b) {
      var c = indexOf(a, b)
      var d = a.indexOf(b);
      // console.log(getMaxLength(b))
      console.log(c, d, c === d)
    }
    test("AAADAABCDAB", "ABCDABD")
    test('aadddaa', 'ddd')
    test("mississippi", "issipi")//-1

    test('acabaabaabcacaabc', 'abaabcac')

    test('bbbbababbbaabbba', 'abb')

[RubyLouvre]

    function findWords(board, words) {
      var visited = new Array(board.length).fill(0).map(function (el, i) {
        return new Array(board[0].length).fill(false)
      })
      var root = new TrieNode().buildTrie(words)
      var res = []

      for(var i = 0; i < board.length; i++){
        for(var j = 0; j < board[0].length; j++){
          if(root.next[board[i][j].charCodeAt(0) -97  ] == null){
            continue
          }
          backtrack(root, i, j)
        }
      }

      function backtrack(node, x, y) {
        if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y]) {
          return;
        }

        var c = board[x][y].charCodeAt(0) - 97
        if(node.next[c] == null){
          return 
        }
        if(node.next[c].word !== null){
          res.push(node.next[c].word );
          node.next[c].word = null
        }

        visited[x][y] = true;
        backtrack(node.next[c], x + 1, y);
        backtrack(node.next[c], x - 1, y);
        backtrack(node.next[c], x, y + 1);
        backtrack(node.next[c], x, y - 1);
        visited[x][y] = false;
      }
      return res;
    }

    var board = [
      ['o', 'a', 'a', 'n'],
      ['e', 't', 'a', 'e'],
      ['i', 'h', 'k', 'r'],
      ['i', 'f', 'l', 'v']
    ]

    class TrieNode {
      constructor(v){
      }
       buildTrie(words) {
            this.root = new TrieNode('');
            var p = this.root
            for (var  word of words) {
                for (var c of word) {
                    if (!p.next[c.charCodeAt(0)-97] ){
                        p.next[c.charCodeAt(0)-97] = new TrieNode(c);
                    }
                    p = p.next[cc.charCodeAt(0)-97];
                }
                p.word = word;
            }
            return this.root;
        }
    }

[RubyLouvre]

https://segmentfault.com/a/1190000018554989