数据结构-字符串

40次阅读

共计 7691 个字符，预计需要花费 20 分钟才能阅读完成。

Create by jsliang on 2019-8-22 07:41:30
Recently revised in 2019-09-16 19:39:15

数组 – 最简单的内存数据结构。

字符串 – 随时可以转换成数字或者数组的简单类型。

重点推荐：String – MDN

  • https://developer.mozilla.org…

jsliang 的联系方式尽在 jsliang 的文档库：https://github.com/LiangJunro…

一 目录

不折腾的前端，和咸鱼有什么区别

| 目录 |
| — |
| 一 目录 |
| 二 前言 |
| 三 字符串的存储结构 |
| 四 字符串的常用知识点 |
|  4.1 字符串 – 查询 |
|  4.2 字符串 – 正则表达式 |
|  4.3 字符串 – 修改 |
|  4.4 字符串 – 转类型 |
|  4.5 字符串 – 大小写 |
|  4.6 字符串 – 去空格 |
| 五 LeetCode – 字符串训练 |
| 六 总结 |

二 前言

返回目录

什么是字符串？

字符串是有零个或者多个字符组成的有序数列。

如果字符串的个数为零，则表明这个字符串为 空串（Null String），长度为 0。空串表示为：''。

如果字符串由空格组成，那么它就不是空串，而是有 n 个空格长度的字符串，例如：' '（它包含了一个空格，所以长度为 1）。

空串和 n 个空格组成的字符串

const nullString = '';
const spaceString = ' ';
console.log(nullString.length); // 0
console.log(spaceString.length); // 1

为什么要引入这个概念呢？

因为在一些场景，你需要知道这个字符串是否为空，从而做某些判断。

例如：

  • 028 – 实现 strStr（implement-strstr）✔

在这题中，就需要判断它是否为空串，如果为空串则返回 0：

var strStr = function(haystack, needle) {if (!needle.length && !haystack.length) {return 0;}
  if (!needle.length) {return 0;}
  // ... 代码省略
};

同时，通过这题，我们还可以引入 子串 的概念：

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。示例:

输入: haystack = "hello", needle = "ll"
输出: 2

在这里，hello 就是 ll 的主串，ll 是 hello 的子串。

如果你初中数学还不赖，那么你大概可以将 ll 当做是 hello 的子集。

到这里，我们开始了解到字符串的一些点，如果你觉得还可以接受，请继续往下看。

三 字符串的存储结构

返回目录

字符串分为两种存储结构：顺序存储和链式存储。

  • 顺序存储：用一组地址连续的存储单元来存储字符串中的字符序列，我们一般用数组来定义。
  • 链式存储：字符串的链式存储，和线性表的链式存储很相似。但是由于字符串结构的特殊性，结构中的每个元素为字符。如果也按照线性表的链式存储，每个节点存放一个字符，那么就会造成很大的空间浪费。

那么问题来了：听不懂是不是。

不管你听不听得懂，反正 jsliang 是不太懂了。

所以咱不管它有的没的先，看完一遍就行了。

是的，不用你以为，要我以为，这篇文章中听我的就好了。/ 滑稽

在这里引入这个，主要是表明，在很多场合，我们会将 字符串转换成数组：

'jsliang'.split(''); // ['j','s','l','i','a','n','g']

从而使用数组中的丰富 API：

  • 数据结构 – 数组

注释 1：不强行理解 顺序存储和链式存储 的概念是因为 jsliang 觉得现在还没有到需要理解的地步。

注释 2：如果你纯粹是个知识大师，却敲不了一行代码，那是不行的，所以 jsliang 强烈推荐在了解概念的同时多练习练习。

四 字符串的常用知识点

返回目录

在上面我们讲解了字符串的基础知识，并且提到了字符串在使用中会转换成数字或者数组，从而更方便我们进行编程。

那么，下面我们就通过字符串相关的 LeetCode 题，来串联一些字符串的 API，从而帮助小伙伴们快速了解其使用方式，加强自己的基础。

应用程序接口（API）是基于编程语言构建的结构，使开发人员更容易地创建复杂的功能。它们抽象了复杂的代码，并提供一些简单的接口规则直接使用。

客户端 JavaScript 中有很多可用的 API：
浏览器 API 内置于 Web 浏览器中，能从浏览器和电脑周边环境中提取数据，并用来做有用的复杂的事情。
第三方 API 缺省情况下不会内置于浏览器中，通常必须在 Web 中的某个地方获取代码和信息。

在此之前，我们先看看字符串有哪些 API，然后开始针对一些常见的 API，在 LeetCode 中锻炼一下思路：

浏览器内置对象只字符串 API

new String; // 在浏览器敲入 new String

// 输出
String {
  length: 0,
  __proto__: {anchor: ƒ anchor(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。big: ƒ big(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。blink: ƒ blink(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。bold: ƒ bold(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。charAt: ƒ charAt(),
    charCodeAt: ƒ charCodeAt(),
    codePointAt: ƒ codePointAt(), // 返回使用 UTF-16 编码的给定位置的值的非负整数。concat: ƒ concat(),
    constructor: ƒ String(), // 用于创造对象的原型对象的特定的函数。endsWith: ƒ endsWith(), // 需要兼容处理（ES6）fixed: ƒ fixed(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。fontcolor: ƒ fontcolor(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。fontsize: ƒ fontsize(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。includes: ƒ includes(),
    indexOf: ƒ indexOf(),
    italics: ƒ italics(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。lastIndexOf: ƒ lastIndexOf(),
    length: 0,
    link: ƒ link(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。localeCompare: ƒ localeCompare(), // 返回一个数字表示是否引用字符串在排序中位于比较字符串的前面，后面，或者二者相同。match: ƒ match(),
    matchAll: ƒ matchAll(),
    normalize: ƒ normalize(), // 返回调用字符串值的 Unicode 标准化形式。padEnd: ƒ padEnd(),
    padStart: ƒ padStart(),
    repeat: ƒ repeat(),
    replace: ƒ replace(),
    search: ƒ search(),
    slice: ƒ slice(),
    small: ƒ small(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。split: ƒ split(),
    startsWith: ƒ startsWith(), // 需要兼容处理（ES6）strike: ƒ strike(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。sub: ƒ sub(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。substr: ƒ substr(), // 避免使用，后期可能被移除
    substring: ƒ substring(),
    sup: ƒ sup(), // 被限制使用，因为只对可用的 HTML 标签和属性提供部分支持。toLocaleLowerCase: ƒ toLocaleLowerCase(),
    toLocaleUpperCase: ƒ toLocaleUpperCase(),
    toLowerCase: ƒ toLowerCase(),
    toString: ƒ toString(),
    toUpperCase: ƒ toUpperCase(),
    trim: ƒ trim(),
    trimEnd: ƒ trimEnd(),
    trimLeft: ƒ trimStart(),
    trimRight: ƒ trimEnd(),
    trimStart: ƒ trimStart(),
    valueOf: ƒ valueOf(), // 返回特定对象的原始值。Symbol(Symbol.iterator): ƒ [Symbol.iterator](),}
}

常用字符串 API

API 功能
str.charAt(index) 返回特定位置的字符。
str.charCodeAt(index) 返回表示给定索引的字符的 Unicode 的值。
str.concat() 连接两个字符串文本，并返回一个新的字符串。
str.includes() 判断一个字符串里是否包含其他字符串。
str.indexOf() 从字符串对象中返回首个被发现的给定值的索引值，如果没有找到则返回 -1。
str.lastIndexOf() 从字符串对象中返回最后一个被发现的给定值的索引值，如果没有找到则返回 -1。
str.length 返回了字符串的长度。
str.match() 使用正则表达式与字符串相比较。
str.matchAll() 返回一个包含所有匹配正则表达式及分组捕获结果的迭代器。
str.padEnd() 在当前字符串尾部填充指定的字符串，直到达到指定的长度。返回一个新的字符串。
str.padStart() 在当前字符串头部填充指定的字符串，直到达到指定的长度。返回一个新的字符串。
str.repeat() 返回指定重复次数的由元素组成的字符串对象。
str.replace() 被用来在正则表达式和字符串直接比较，然后用新的子串来替换被匹配的子串。
str.search() 对正则表达式和指定字符串进行匹配搜索，返回第一个出现的匹配项的下标。
str.slice() 摘取一个字符串区域，返回一个新的字符串。
str.split() 通过分离字符串成子串，将字符串对象分割成字符串数组。
str.substring() 返回在字符串中指定两个下标之间的字符。
str.toLocaleLowerCase() 根据当前区域设置，将符串中的字符转换成小写。对于大多数语言来说，toLowerCase 的返回值是一致的。
str.toLocaleUpperCase() 根据当前区域设置，将字符串中的字符转换成大写，对于大多数语言来说，toUpperCase 的返回值是一致的。
str.toLowerCase() 将字符串转换成小写并返回。
str.toUpperCase() 将字符串转换成大写并返回。
type.toString() 返回用字符串表示的特定对象。
str.trim() 从字符串的开始和结尾去除空格。
str.trimEnd() / str.trimRight() 从字符串的右侧去除空格。
str.trimStart() / str.trimLeft() 从字符串的左侧去除空格。

如上，我们列出了 23 种 可能 比较常用的 字符串 API。

但是，如果仅仅这样列出来，那还不如直接看 MDN 关于 JavaScript 字符串的讲解：

  • String – MDN

所以，下面将进行归类，并通过 LeetCode 进行详细剖析学习。

参考文献

  • String – MDN
  • JavaScript 中字符串的常见 api 操作（偏 ES5）

4.1 字符串 – 查询

返回目录

  1. str.length：返回了字符串的长度。详细学习
  2. str.charAt(index)：返回特定位置的字符。详细学习
  3. str.charCodeAt(index)：返回表示给定索引的字符的 Unicode 的值。详细学习
  4. str.includes(searchString, fromIndex))：判断一个字符串里是否包含其他字符串。详细学习
  5. str.indexOf(searchString, fromIndex)：从字符串对象中返回首个被发现的给定值的索引值，如果没有找到则返回 -1。详细学习
  6. str.lastIndexOf(searchString, fromIndex)：从字符串对象中返回最后一个被发现的给定值的索引值，如果没有找到则返回 -1。详细学习
  7. str.substring(indexStart, indexEnd)：返回在字符串中指定两个下标之间的字符。详细学习

4.2 字符串 – 正则表达式

返回目录

  1. str.match(regexp)：使用正则表达式与字符串相比较。详细学习
  2. str.matchAll(regexp)：返回一个包含所有匹配正则表达式及分组捕获结果的迭代器。详细学习
  3. str.replace(regexp |substr, newSubStr| function)：被用来在正则表达式和字符串直接比较，然后用新的子串来替换被匹配的子串。详细学习
  4. str.search(regexp)：对正则表达式和指定字符串进行匹配搜索，返回第一个出现的匹配项的下标。详细学习

4.3 字符串 – 修改

返回目录

  1. str.concat(string2, string3, ..., stringN)：连接两个字符串文本，并返回一个新的字符串。详细学习
  2. str.padStart(targetLength, padString)：在当前字符串头部填充指定的字符串，直到达到指定的长度。返回一个新的字符串。详细学习
  3. str.padEnd(targetLength, padString)：在当前字符串尾部填充指定的字符串，直到达到指定的长度。返回一个新的字符串。详细学习
  4. str.repeat(count)：返回指定重复次数的由元素组成的字符串对象。详细学习
  5. str.slice(beginIndex, endIndex)：摘取一个字符串区域，返回一个新的字符串。详细学习

4.4 字符串 – 转类型

返回目录

  1. str.split(separator, limit)：（字符串转数组）通过分离字符串成子串，将字符串对象分割成字符串数组。详细学习
  2. type.toString()：（其他类型转字符串）返回用字符串表示的特定对象。详细学习

4.5 字符串 – 大小写

返回目录

  1. str.toLocaleLowerCase() / str.toLowerCase()：根据当前区域设置，将符串中的字符转换成小写。对于大多数语言来说，toLowerCase 的返回值是一致的。详细学习
  2. str.toLocaleUpperCase() / str.toUpperCase()：根据当前区域设置，将字符串中的字符转换成大写，对于大多数语言来说，toUpperCase 的返回值是一致的。详细学习

4.6 字符串 – 去空格

返回目录

  1. str.trim()：从字符串的开始和结尾去除空格。详细学习
  2. str.trimStart() / str.trimLeft()：从字符串的左侧去除空格。详细学习
  3. str.trimEnd() / str.trimRight()：从字符串的右侧去除空格。详细学习

五 LeetCode – 字符串训练

返回目录

首先，由于 jsliang 在编写时发现，如果针对某个 API 然后找到对应的某个题给小伙伴尝试，无异议饮鸩止渴，对后期成长是没有帮助的。

然后，jsliang 尝试攻略的这些题目的覆盖范围可能不是小伙伴想要的（即做了对字符串没法非常深入了解，覆盖面也可能不全），所以小伙伴可以尝试自己选题：

  • LeetCode 字符串专栏

最后，贴上一些目前 jsliang 已经攻略的字符串题目，希望对小伙伴们有所帮助：

  • 003 – 无重复长度的最长子串（longest-substring-without-repeating-characters）
  • 005 – 最长回文子串（longest-palindromic-substring）
  • 008 – 字符串转换整数（string-to-integer-atoi）
  • 013 – 罗马数字转整数（roman-to-integer）
  • 014 – 最长公共前缀（longest-common-prefix）
  • 020 – 有效的括号（valid-parentheses）
  • 028 – 实现 strStr（implement-strstr）
  • 038 – 报数（count-and-say）
  • 049 – 字母异位词分组（group-anagrams）
  • 058 – 最后一个单词的长度（length-of-last-word）
  • 067 – 二进制求和（add-binary）
  • 125 – 验证回文串（valid-palindrome）
  • 344 – 反转字符串（reverse-string）
  • 345 – 反转字符串中的元音字母（reverse-vowels-of-a-string）
  • 383 – 赎金信（ransom-note）
  • 387 – 字符串中的第一个唯一字符（first-unique-character-in-a-string）
  • 415 – 字符串相加（add-strings）
  • 434 – 字符串中的单词数（number-of-segments-in-a-string）
  • 443 – 压缩字符串（string-compression）
  • 459 – 重复的字符串（repeated-substring-pattern）

六 总结

返回目录

经过前面一系列的折腾，我们基本对字符串的各种操作有所了解，虽然谈不上 精通，但是支持日常工作是毫无问题的。

毕竟在日常工作中，字符串很常见，所以我们还是需要去发掘它，使用它的。

那么，字符串的讲解就到此为止啦，咱们下个知识点再见~

如果你觉得 jsliang 写得很 OK，欢迎点赞、留言、加微信好友、关注微信公众号等。

咱们，将继续探索，扎实编程基础，了解更多的数据结构和算法！

jsliang 的联系方式尽在 jsliang 的文档库：https://github.com/LiangJunro…

不折腾的前端，和咸鱼有什么区别！

jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。

扫描上方二维码，关注 jsliang 的公众号，让我们一起折腾！

<img alt=” 知识共享许可协议 ” style=”border-width:0″ src=”https://i.creativecommons.org…; />
<span xmlns:dct=”http://purl.org/dc/terms/&quot; property=”dct:title”>jsliang 的文档库 </span> 由 梁峻荣 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
基于 https://github.com/LiangJunro… 上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/l… 处获得。

正文完
leetcode 字符串 算法-数据结构
发表至： javascript
2019-09-17
 0
关于javascript:分享一个Vue项目实践方案
关于javascript:tiptap-基于-vue-的优雅流畅的开源富文本编辑器
转Vue中对From表单中的Table表格中的输入项进行验证
关于javascript:web高仿樊登H5微信音乐播放悬浮球效果