Amanda-Zhang
追梦女一枚
FRIENDS
friendAfriendB

zj字符串类算法题

2021-05-24 -leetcode -算法
Word count: 3.9k | Reading time: 17min

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

题解

遇到此类括号匹配题目，首先想到的就是栈了。

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；建立哈希表 Map构建左右括号对应关系：key左括号，value 右括号；这样查询 2 个括号是否对应只需 O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。

解法一：自己做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  
  let s1 = s.split("");
  if(s1.length % 2){
      return false;
  }
   let stk = [];
   const m = new Map([['(',')'],['[',']'],['{','}']]);
   for(let i of s1){
       if(m.get(i)){
           stk.push(i);
       }else{
           if(i !== m.get(stk[stk.length-1])){
               return false;
           }else{
               stk.pop();
           }
       }
   }
   return !stk.length;
};

解法二：模仿别人做的。其实道理和解法一相同，只是建map的时候顺序有些不同，就会执行不同的操作，详情见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//模仿别人做的
var isValid = function(s) {
    if(s.length % 2){
        return false;
    }
    let stk = [];
    const mm = new Map([[')','('],[']','['],['}','{']]);
    for(let i of s){
        if(mm.get(i)){
            if(stk[stk.length-1] !== mm.get(i)) return false;
            else stk.pop();
        }else{
            stk.push(i)
        }
    }
    return !stk.length;
};

解法三：不利用Map的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var isValid = function(s) {
     if(s.length % 2){
        return false;
    }
    let stk = [];
    for(let i of s){
        switch(i){
          case "(":
          case "[":
          case "{":
            stk.push(i);
            break;
          case ")":
            if(stk.pop()!== "(") return false;
            break;
          case "]":
            if(stk.pop()!== "[") return false;
            break;
           case "}":
            if(stk.pop()!== "{") return false;
            break;
        }
    }
    return !stk.length;
};

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = “3[a]2[bc]”
输出：”aaabcbc”

示例 2：

输入：s = “3[a2[c]]”
输出：”accaccacc”

示例 3：

输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”

示例 4：

输入：s = “abc3[cd]xyz”
输出：”abccdcdcdxyz”

题解

用栈来做吧（多看多复习，这个有点绕，画画图最好！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    let numStack = [];        // 存倍数的栈
    let strStack = [];        // 存 待拼接的str 的栈
    let num = 0;              // 倍数的“搬运工”
    let result = '';          // 字符串的“搬运工”
    for (const char of s) {   // 逐字符扫描
        if (!isNaN(char)) {   // 遇到数字
            num = num * 10 + Number(char); // 算出倍数
        } else if (char == '[') {  // 遇到 [
            strStack.push(result); // result串入栈
            result = '';           // 入栈后清零
            numStack.push(num);    // 倍数num进入栈等待
            num = 0;               // 入栈后清零
        } else if (char == ']') {  // 遇到 ]，两个栈的栈顶出栈
            let repeatTimes = numStack.pop(); // 获取拷贝次数
            result = strStack.pop() + result.repeat(repeatTimes); // 构建子串
        } else {                   
            result += char;        // 遇到字母，追加给result串
        }
    }
    return result;
};

208. 实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

题解

Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：

指向子节点的指针数组 children。对于本题而言，数组长度为 26，即小写英文字母的数量。此时 children[0]对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。

布尔字段 isEnd，表示该节点是否为字符串的结尾。

插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 children数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。

重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。

重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var Trie = function() {
    this.children = {};
};
// 一、前缀树中插入字符串 word
Trie.prototype.insert = function(word) {
    let node = this.children;
    //1、子节点存在。沿着指针移动到子节点，继续处理下一个字符。
    //2、子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。    
    for (const ch of word) {
        if (!node[ch]) {
            node[ch] = {};
        }
        node = node[ch];
    }
    // isEnd：表示该节点是否为字符串的结尾
    node.isEnd = true;
};
// 二、如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false
Trie.prototype.search = function(word) {
    const node = this.searchPrefix(word);
    // 若搜索到了前缀的末尾，就说明字典树中存在该前缀。
    // 此外，若前缀末尾对应节点的isEnd 为真，则说明字典树中存在该字符串。
    return node !== undefined && node.isEnd !== undefined;
};
// 三、如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
Trie.prototype.startsWith = function(prefix) {
    return this.searchPrefix(prefix);
};

Trie.prototype.searchPrefix = function(prefix) {
    let node = this.children; 
    //1、子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
    //2、子节点不存在。说明字典树中不包含该前缀，返回空指针。
    for (const ch of prefix) {
        if (!node[ch]) {
            return false;
        }
        node = node[ch];
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Initialize your data structure here.
 */
var Trie = function() {
  this.children={}
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
// 这个word是一多叉树 
Trie.prototype.insert = function(word) {
  let node = this.children
  // 节点值作为key值
  for(let ch of word){
    if(!node[ch]){
      node[ch]={}
    }
    node = node[ch]
  }
  node.isEnd = true
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  let node = this.children
  for(let ch of word){
    if(!node[ch]){
      return false
    }
    node = node[ch]
  }
  return node!==undefined&&node.isEnd!==undefined

};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
  let node = this.children
  for(let ch of prefix){
    if(!node[ch]){
      return false
    }
    node = node[ch]
  }
  return true
};

211. 添加与搜索单词 - 数据结构设计

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

题解

还是可以用字典树。如上题的思路。

对于记录/查找单词的情景，有种数据结构非常高效：Trie。我们可以构造一棵字典树，每次调用 addWord 时候，将单词存入字典树。注意：当调用 search 进行查找的时候，如果当前字符不是.，那么就按照字典树的查找逻辑；否则，由于是通配符，要遍历当前的节点的 next 中的所有字符，这个过程和 DFS 一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/**
 * Initialize your data structure here.
 */
var WordDictionary = function () {
  this.root = {};
};

/**
 * Adds a word into the data structure.
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
  let node = this.root;
  for (let c of word) {
    if (!node[c]) {
      node[c] = {};
    }
    node = node[c];
  }
  if (!node.END) {
    node.END = true;
  }
};

/**
 * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
  function _search(word, root) {
    let node = root;
    for (let i = 0; i < word.length; i++) {
      let c = word[i];
      if (!node[c]) {
        if (c === ".") {
          for (let p in node) {
            if (!p || p === "END") continue;
            if (_search(word.slice(i + 1), node[p])) {
              return true;
            }
          }
        }
        return false;
      }
      node = node[c];
    }
    return node && !!node.END;
  }
  return _search(word, this.root);
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

389. 找不同

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = “abcd”, t = “abcde”
输出：”e”
解释：’e’ 是那个被添加的字母。

示例 2：

输入：s = “”, t = “y”
输出：”y”

示例 3：

输入：s = “a”, t = “aa”
输出：”a”

示例 4：

输入：s = “ae”, t = “aea”
输出：”a”

题解

1.求和方法

将字符串 s 中每个字符的 ASCII 码的值求和，得到 sum1；对字符串 t 同样的方法得到 sum2。两者的差值 sum2-sum1 即代表了被添加的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    let sum1 = 0,sum2 =0;
    for(let i =0;i<s.length;i++){
        sum1 += s.charCodeAt(i);    //返回索引处的值的unicode值
    }
    for(let j =0;j<t.length;j++){
        sum2 += t.charCodeAt(j);
    }
    return String.fromCharCode(sum2-sum1);
}

2.计数方法

首先遍历字符串 s，对其中的每个字符都将计数值加 1；然后遍历字符串 t，对其中的每个字符都将计数值减 1。当发现某个字符计数值为负数时，说明该字符在字符串 t中出现的次数大于在字符串 s中出现的次数，因此该字符为被添加的字符。

1
2
3
4
5
6
7
8
9
10
11
12
var findTheDifference = function(s, t) {
    const m = new Array(26).fill(0);
    for(s of s){
        m[s.charCodeAt()-a.charCodeAt()]++;
    }
    for(t of t){
        m[t.charCodeAt()-a.charCodeAt()]--;
        if(m[t.charCodeAt()-a.charCodeAt()]<0){
            return t;
        }
    }
}

3.位运算（运用异或）

如果将两个字符串拼接成一个字符串，则问题转换成求字符串中出现奇数次的字符。类似于「136. 只出现一次的数字」，我们使用位运算的技巧解决本题。（位运算不是很熟，需要多练）

1
2
3
4
5
6
7
8
9
10
var findTheDifference = function(s, t) {
    let ret = 0;
    for (const ch of s) {
        ret ^= ch.charCodeAt();
    }
    for (const ch of t) {
        ret ^= ch.charCodeAt();
    }
    return String.fromCharCode(ret);//多余的那个字符的ASCII值转为字符
};

4.HashMap 方法（自己最开始想到的一种方法，但是我忽略了哈希表里面的key是不能重复的，如有重复，后面的会覆盖前面的key）方法是遍历第一个字符串标记出现的字符数量，再遍历第二个减去出现的数量，直到遇到为 0 或者原哈希表就不存在的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var findTheDifference = function(s, t) {
    var map = new Map();
    for(let i of s){
        const val = map.get(i);
        map.set(i,val === undefined? 1:val+1);
    }
    for(let j of t){
        const val = map.get(j);
        if(map.has(j)&&val>0){
            map.set(j,val-1);
        }
        if(!map.has(j)||val==0){
            return j;
        }
       
    }
}

290. 单词规律

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, str = “dog cat cat dog”
输出: true

示例 2:

输入:pattern = “abba”, str = “dog cat cat fish”
输出: false

示例 3:

输入: pattern = “aaaa”, str = “dog cat cat dog”
输出: false

示例 4:

输入: pattern = “abba”, str = “dog dog dog dog”
输出: false

题解

（1）indexOf()派上用场了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string} pattern
 * @param {string} str
 * @return {boolean}
 */
var wordPattern = function(pattern, str) {
    var arr = str.split(' ');
    if(pattern.length!=arr.length) return false;
    for(var i=0;i<pattern.length;i++){
        if(pattern.indexOf(pattern[i])!=arr.indexOf(arr[i])){
            return false;
        }
    }
    return true;
};

（2）map用法（注意：这里为什么要用两个map,因为两者是一一对应的，一个字符串的字符对应着唯一的单词，一个唯一的单词又对应着唯一的字符串，即双射，需要两个map来保证一一对应）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var wordPattern = function(pattern, str) {
    var arr = str.split(' ');
    var map = new Map();
    var maps = new Map();
    if(pattern.length!=arr.length) return false;
    for(var i=0;i<pattern.length;i++){
        
        if(maps.has(arr[i])==false){
            maps.set(arr[i],pattern[i]);
        }else{
            if(maps.get(arr[i])!=pattern[i]){
                return false
            }
        }
        if(map.has(pattern[i])==false){
            map.set(pattern[i],arr[i]);
        }else{
            if(map.get(pattern[i])!=arr[i]){
                return false
            }
        }

    }
    return true;
};
//这是其中的一个解法

387. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

1
2
3
4
5
s = "leetcode"
返回 0

s = "loveleetcode"
返回 2
题解

1.使用Map遍历两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    let map = new Map();
    for(let i=0;i<s.length;i++){
        map.set(s[i],(map.get(s[i])||0)+1);
    }
    for(let j=0;j<s.length; j++){
        if(map.get(s[j])==1){
            return j;
        }
    }
    return -1;
};
  1. 利用indexOf和lastIndexOf来判断
1
2
3
4
5
6
7
8
9
//第二种  利用indexOf和lastIndexOf来判断
var firstUniqChar = function(s) {
    for(let i=0;i<s.length;i++){
        if(s.indexOf(s[i]) === s.lastIndexOf(s[i])){
            return i;
        }
    }
    return -1;
};

Author: Amanda-Zhang

Link: http://chunchunya.github.io/2021/04/10/4-9_zj%E7%AE%97%E6%B3%95%E7%B1%BB%E9%A2%98%E7%9B%AE/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
Js中for in 和for of的区别NextPost >
链表类题目
CATALOG
  1. 1. 20. 有效的括号
  2. 2. 题解
  3. 3. 394. 字符串解码
  4. 4. 题解
  5. 5. 208. 实现 Trie (前缀树)
  6. 6.
  7. 7. 题解
  8. 8. 211. 添加与搜索单词 - 数据结构设计
  9. 9. 题解
  10. 10. 389. 找不同
  11. 11. 题解
  12. 12. 290. 单词规律
  13. 13. 题解
  14. 14. 387. 字符串中的第一个唯一字符
    1. 14.1. 题解