JavaScript 算法

【数据结构与算法】字符串（JavaScript版详解）

By yesmore on 2021-08-13
阅读时间 19 分钟
文章共 4.6k 字
阅读量 次

要点：字符串、常见字符串方法

先知：

一、串

1.1 定义

串（string） 是由零个或多个字符组成的有限序列，又名叫 字符串

1.2 串的逻辑结构

串 的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符。

因此，对于串的基本操作与线性表是有很大差别的：

  • 线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素；

  • 但串中更多的是查找子串位置，得到指定位置子串，替换子串等操作

1.3 串的存储结构

串 的存储结构与线性表相同，分为两种：

  • 顺序存储结构

  • 链式存储结构

串的顺序存储结构

串的顺序存储结构是用 一组地址连续的存储单元 来存储串中的字符序列。一般是用定长数组来定义

由于是定长数组，因此就会存在一个预定义的最大串长度；

一般可以将实际的串长度值保存在数组 0 下标位置，也可以放在数组最后一个下标位置；

也有些语言使用在串值后面加一个不计入串长度的结束标记符（比如\0）来表示串值得终结，这样就无需使用数字进行记录

串的链式存储结构

对于串的链式存储结构，与线性表是相似的；

但由于串结构的特殊性（结构中的每个元素数据都是一个字符），如果也简单地将每个链结点存储一个字符，就会存在很大的空间浪费；

因此，一个结点可以考虑存放多个字符，如果最后一个结点未被占满时，可以使用 “#” 或其他非串值字符补全

串的链式存储结构除了在链接串与串操作时有一定的方便之外

总的来说不如顺序存储灵活，性能也不如顺序存储结构好

二、JavaScript中的串

2.1 定义

字符串就是一个或多个排列在一起的字符，放在单引号或双引号之中。

‘abc’
“abc”

js里的字符串类似于数组，都是一个一个字符拼凑在一起组成的，因此可以用length属性取得字符串的长度

1
2
var str = "hello"
str.length; // 5

2.2 字符串常用的一些方法

1.charAt()
1
str.charAt(n)

作用：返回字符串的第 n 个字符，如果不在 0~str.length-1之间，则返回一个空字符串。

1
2
3
var str = "javascript";
str.charAt(2);  // 'v'
str.charAt(12); // ''
2.indexOf()
1
indexOf(substr[,start])

作用：返回 substr 在字符串 str 中首次出现的位置,从 start 位置开始查找，如果不存在，则返回 -1。

start可以是任意整数，默认值为 0。如果 start < 0 则查找整个字符串（如同传进了 0）。如果 start >= str.length，则该方法返回 -1，除非被查找的字符串是一个空字符串，此时返回 str.length.

1
2
3
4
5
var str =   "javascript"  ;
str.indexOf('s'); // 1  
str.indexOf(  's'  ,6);   // -1  
str.indexOf(  ''  ,11);   // 10  
str.indexOf(  ''  ,8);   // 8
3.lastIndexOf()
1
lastIndexOf(substr[,start])

作用：返回 substr 在字符串 str 中最后出现的位置,从 start 位置 向前开始查找，如果不存在，则返回 -1。

1
'lastindex'.lastIndexOf(  'a'  );   // 1
4.substring()
1
str.substring(start[, end])

作用：返回从 start 到 end（不包括）之间的字符，start、end均为 非负整数。若结束参数(end)省略，则表示从start位置一直截取到最后。

1
2
3
var  str =   'abcdefg'  ;  str.substring(1, 4);   //"bcd"  
str.substring(1);   // "bcdefg"  
str.substring(-1);   //"abcdefg" 传入负值时会视为0
5.slice()
1
str.slice(start[,end])

作用：返回从 start 到 end （不包括）之间的字符，可传负值

1
2
var  str =   'this is awesome'  ;  
str.slice(4, -1);   //" is awesom"
6. substr()
1
str.slice(start[,end])

作用：返回 str 中从指定位置开始到指定长度的子字符串，start可为负值

1
2
3
var  str =   "Just give me a reason"  ;  
str.substr(5, 10);   // "give me a "  
str.substr(-4, 2);   // "as"
7. replace()
1
str.replace(regexp|substr, newSubStr|function  )

作用：替换 str 的子字符串

1
2
var  str =   "do you love me"  ;  
str.replace(  'love'  ,  'hate'  );   // "do you hate me"
1
str.search(regexp)

作用：查找 str 与一个正则表达式是否匹配。如果匹配成功，则返回正则表达式在字符串中首次匹配项的索引；否则，返回 -1。如果参数传入的是一个非正则表达式对象，则会使用 new RegExp(obj) 隐式地将其转换为正则表达式对象

1
2
3
4
5
var str = 'I love JavaScript!'  ;  
str.search(/java/);   // -1  
str.search(/Java/);   // 7  
str.search(/java/i);   // 7  
str.search(  'Java'  );   // 7
9. match()
1
str.match(regexp)

作用：返回一个包含匹配结果的数组，如果没有匹配项，则返回 null。如果参数传入的是一个非正则表达式对象，则会使用 new RegExp(obj) 隐式地将其转换为正则表达式对象

1
2
3
var str =   'Javascript java'  ;  str.match(/Java/);   // ["Java"]  
str.match(/Java/gi);   // ["java", "Java"]  
str.match(/ab/g);   // null
10. split()
1
str.split([separator][, limit])

= >返回一个数组，分隔符 separator 可以是一个字符串或正则表达式

1
2
3
4
var  str =   "Hello?World!"  ;  str.split();   // ["Hello?World!"]  
str.split(  ''  );   // ["H", "e", "l", "l", "o", "?", "W", "o", "r", "l", "d", "!"]  
str.split(  '?'  );   // ["Hello", "World!"]  
str.split(  ''  ,5);   // ["H", "e", "l", "l", "o"]
11. trim()
1
str.trim()

作用：去除 str 开头和结尾处的空白字符，返回 str 的一个副本，不影响字符串本身的值

1
2
3
var  str =   ' abc '  ;  
str.trim();   // 'abc'  
console.log(str);   // ' abc '
12. toLowerCase()
1
str.toLowerCase()

作用：将 str 转换为小写，并返回 str 的一个副本，不影响字符串本身的值

1
2
3
var  str =   'JavaScript'  ;  
str.toLowerCase();   // 'javascript'  
console.log(str);   // 'JavaScript'
13. toUpperCase()
1
str.toUpperCase()

作用：将 str 转换为大写，并返回 str 的一个副本，不影响字符串本身的值

1
2
3
var  str =   'JavaScript'  ;  
str.toUpperCase();   // 'JAVASCRIPT'  
console.log(str);   // 'JavaScript'

三、JavaScript正则表达式

关于正则匹配详见：MDN

3.1 元字符

( [ { \ ^ $ | ) ? * + .

3.2 预定义的特殊字符

字符 正则 描述
\t /\t/ 制表符
\n /\n/ 换行符
\r /\r/ 回车符
\f /\f/ 换页符
\a /\a/ alert字符
\e /\e/ escape字符
\cX /\cX/ 与X相对应的控制字符
\b /\b/ 与回退字符
\v /\v/ 垂直制表符
\0 /\0/ 空字符

3.3 字符类

简单类

原则上正则的一个字符对应一个字符，我们可以用[]把它们括起来，让[]这个整体对应一个字符。如

1
2
3
4
5
alert(/ruby/.test(  "ruby"  ));  //true  
alert(/[abc]/.test(  "a"  ));  //true  
alert(/[abc]/.test(  "b"  ));  //true  
alert(/[abc]/.test(  "c"  ));  //true  
alert(  "a bat ,a Cat,a fAt bat ,a faT cat".match(/[bcf]at/gi));  //bat,Cat,fAt,bat,faT,cat
负向类

也是在那个括号里做文章，前面加个元字符进行取反，表示匹配不能为括号里面的字符。

1
2
3
4
alert(/[^abc]/.test(  "a"  ));  //false  
alert(/[^abc]/.test(  "b"  ));  //false  
alert(/[^abc]/.test(  "6"  ));  //true  
alert(/[^abc]/.test(  "gg"  ));  //true
范围类

还是在那个中括号里面做文章。有时匹配的东西过多，而且类型又相同，全部输入太麻烦，我们可以用它。特征就是在中间加了个横线。

组合类

还是在那个中括号里面做文章。允许用中括号匹配不同类型的单个字符。

1
2
3
4
5
6
7
8
9
10
11
12
alert(/[a-f]/.test(  "b"  ));  //true  
alert(/[a-f]/.test(  "k"  ));  //false  
alert(/[a-z]/.test(  "h"  ));  //true  
alert(/[A-Z]/.test(  "gg"  ));  //false  
alert(/[^H-Y]/.test(  "G"  ));  //true  
alert(/[0-9]/.test(  "8"  ));  //true  
alert(/[^7-9]/.test(  "6"  ));  //true
alert(/[a-m1-5\n]/.test(  "a"  ))  //true  
alert(/[a-m1-5\n]/.test(  "3"  ))  //true  
var  a =   "\n\        "  
alert(/[a-m1-5\n]/.test(a))  //true  
alert(/[a-m1-5\n]/.test(  "r"  ))  //false
预定义类

还是在那个中括号里面做文章，不过它好像已经走到尽头了。由于是中括号的马甲，因此它们还是对应一个字符。

字符 等同于 描述
. [^\n\r] 除了换行和回车之外的任意字符
\d [0-9] 数字字符
\D [^0-9] 非数字字符
\s [ \t\n\x0B\f\r] 空白字符
\S [^ \t\n\x0B\f\r] 非空白字符
\w [a-zA-Z_0-9] 单词字符(所有的字母)
\W [^a-zA-Z_0-9] 非单词字符 
1
2
3
4
5
6
7
8
9
10
11
12
13
alert(/\d/.test(  "3"  ))  //true  
alert(/\d/.test(  "w"  ))  //false  
alert(/\D/.test(  "w"  ))  //true  
alert(/\w/.test(  "w"  ))  //true  
alert(/\w/.test(  "司"  ))  //false  
alert(/\W/.test(  "徒"  ))  //true  
alert(/\s/.test(  " "  ))  //true  
alert(/\S/.test(  " "  ))  //false  
alert(/\S/.test(  "正"  ))  //true  
alert(/./.test(  "美"  ))  //true  
alert(/./.test(  " "  ))  //true  
var  a =   "\n\       "  
alert(/./.test(a))  //true

3.4 量词

由于元字符与特殊字符或字符类或者它们的组合（中括号）甚至它们的马甲（预定义类）都是一对一进行匹配。我们要匹配“司徒正美这个词”，最简单都要/…/，如果长到50多个字符岂不是要死人。因此我们逼切需要一个简单的操作，来处理这数量关系。

简单量词

代码 类型 描述
? 软性量词 出现零次或一次
* 软性量词 出现零次或多次(任意次)
+ 软性量词 出现一次或多次（至道一次）
{n} 硬性量词 对应零次或者n次
{n,m} 软性量词 至少出现n次但不超过m次
{n,} 软性量词 至少出现n次(+的升级版) 
1
2
3
4
5
6
7
8
9
10
alert(/..../.test(  "司徒正美"  ))  //true  
alert(/司徒正美/.test(  "司徒正美"  ))  //true 
alert(/[\u4e00-\u9fa5]{4}/.test(  "司徒正美"  ))  //true  
alert(/[\u4e00-\u9fa5]{4}/.test(  "司徒正美55"  ))  //true  
alert(/^[\u4e00-\u9fa5]+$/.test(  "正则表达式"  ))  //true  
alert(/^[\u4e00-\u9fa5]+$/.test(  "正则表达式&*@@"  ))  //false  
alert(/\d{6}/.test(  "123456"  ))  //true  
alert(/[ruby]{2}/.test(  "rr"  ))  //true  
alert(/[ruby]{2}/.test(  "ru"  ))  //true  
alert(/[ruby]{2}/.test(  "ry"  ))  //true

/[\u4e00-\u9fa5]/用于匹配单个汉字。

贪婪量词，惰性量词与支配性量词

贪婪量词，上面提到的所有简单量词。就像成语中说的巴蛇吞象那样，一口吞下整个字符串，发现吞不下（匹配不了），再从后面一点点吐出来（去掉最后一个字符，再看这时这个整个字符串是否匹配，不断这样重复直到长度为零）

隋性量词，在简单量词后加问号。由于太懒了，先吃了前面第一个字符，如果不饱再捏起多添加一个（发现不匹配，就读下第二个，与最初的组成一个有两个字符串的字符串再尝试匹配，如果再不匹配，再吃一个组成拥有三个字符的字符串……）。其工作方式与贪婪量词相反。

支配性量词，在简单量词后加加号。上面两种都有个不断尝试的过程，而支配性量词却只尝试一次，不合口味就算了。就像一个出身高贵居支配地位的公主。但你也可以说它是最懒量词。由于javascript不支持，所以它连出场的机会也没有了。

1
2
3
4
5
6
7
8
9
var re1 = /.*bbb/g;  //贪婪  
var re2 = /.*?bbb/g;  //惰性  
// var re3 = /.*+bbb/g;//支配性,javascript不支持，IE与所有最新的标准浏览器都报错  
alert(re1.test(  "abbbaabbbaaabbbb1234"  )+  ""  );  //true  
alert(re1.exec(  "abbbaabbbaaabbbb1234"  )+  ""  );  //null  
alert(  "abbbaabbbaaabbbb1234"  .match(re1)+  ""  );  //abbbaabbbaaabbbb
alert(re2.test(  "abbbaabbbaaabbbb1234"  )+  ""  );  //true  
alert(re2.exec(  "abbbaabbbaaabbbb1234"  )+  ""  );  //aabbb  
alert(  "abbbaabbbaaabbbb1234"  .match(re2)+  ""  );  //abbb,aabbb,aaabbb

3.5 分组

到目前为止，我们只能一个字符到匹配，虽然量词的出现，能帮助我们处理一排密紧密相连的同类型字符。但这是不够的，下面该轮到小括号出场了，中括号表示范围内选择，大括号表示重复次数。小括号允许我们重复多个字符。

1
2
3
4
5
6
//分组+量词  
alert(/(dog){2}/.test(  "dogdog"  ))  //true  
//分组+范围  
alert(  "baddad"  .match(/([bd]ad?)*/))  //baddad,dad  
//分组+分组  
alert(  "mon and dad"  .match(/(mon( and dad)?)/))  //mon and dad,mon and dad, and dad

3.6 反向引用

反向引用标识由正则表达式中的匹配组捕获的子字符串。每个反向引用都由一个编号或名称来标识，并通过“\编号”表示法进行引用。

1
2
3
4
5
6
7
var color =   "#990000"  ;  
/  #(\d+)/.test(color);  
alert(RegExp.$1);  //990000
alert(/(dog)\1/.test(  "dogdog"  ))  //true
var num =   "1234 5678"  ;
var newNum = num.replace(/(\d{4}) (\d{4})/,  "$2 $1"  );  
alert(newNum)

3.7 候选

继续在分组上做文章。在分组中插入管道符（“|”），把它划分为两个或多个候多项。

1
2
3
var  reg = /(red|black|yellow)!!/;  alert(reg.test(  "red!!"  ))  //true  
alert(reg.test(  "black!!"  ))  //true  
alert(reg.test(  "yellow!!"  ))  //true

3.8 非捕获性分组

并不是所有分组都能创建反向引用，有一种特别的分组称之为非捕获性分组，它是不会创建反向引用。反之，就是捕获性分组。要创建一个非捕获性分组，只要在分组的左括号的后面紧跟一个问号与冒号就行了。

1
2
3
var  color =   "#990000"  ;
/  #(?:\d+)/.test(color); 
alert(RegExp.$1);  //""

题目，移除所有标签，只留下innerText!

1
2
3
var html =   "<p><a href='http://www.cnblogs.com/rubylouvre/'>Ruby Louvre</a>by <em>司徒正美</em></p>"  ;  
var text = html.replace(/<(?:.|\s)*?>/g,   ""  );  
alert(text)

注意：javascript不存在命名分组

前瞻

继续在分组内做文章。前瞻与后瞻其实都属于零宽断言，但javascript不支持后瞻。

零宽断言
正则 名称 描述
(?=exp) 正向前瞻 匹配exp前面的位置
(?!exp) 负向前瞻 匹配后面不是exp的位置
(?<=exp) 正向后瞻 匹配exp后面的位置不支持
(?<!exp) 负向后瞻 匹配前面不是exp的位置不支持

正向前瞻用来检查接下来的出现的是不是某个特定的字符集。而负向前瞻则是检查接下来的不应该出现的特定字符串集。零宽断言是不会被捕获的。

1
2
3
4
5
6
7
8
9
10
11
12
var  str1 =   "bedroom"  ;  
var  str2 =   "bedding"  ;  
var  reBed = /(bed(?=room))  ///在我们捕获bed这个字符串时，抢先去看接下来的字符串是不是room  
alert(reBed.test(str1));  //true 
alert(RegExp.$1)  //bed  
alert(RegExp.$2 ===   ""  )  //true 
alert(reBed.test(str2))  //false
var  str1 =   "bedroom"  ; 
var  str2 =   "bedding"  ; 
var  reBed = /(bed(?!room))/   //要来它后面不能是room  
alert(reBed.test(str1))  //false  
alert(reBed.test(str2))  //true

题目，移除hr以外的所有标签，只留下innerText!

1
2
3
var  html =   "<p><a href='http://www.cnblogs.com/rubylouvre/'>Ruby Louvre</a></p><hr/><p>by <em>司徒正美</em></p>"  ; 
var  text = html.replace(/<(?!hr)(?:.|\s)*?>/ig,  ""  ) 
alert(text)  //Ruby Louvre<hr/>by 司徒正美
边界

一个要与字符类合用的东西。

边界
正则 名称 描述
^ 开头 注意不能紧跟于左中括号的后面
$ 结尾
\b 单词边界 指[a-zA-Z_0-9]之外的字符
\B 非单词边界

题目，设计一个字符串原型方法，实现首字母大写！

1
2
3
4
5
6
7
var  a =   "ruby"  ;   
String.prototype.capitalize =   function  () {  
    return  this.replace(/^\w/,   function  (s) {        
        return  s.toUpperCase();       
    });   
}  
alert(a.capitalize())  //Ruby

单词边界举例。要匹配的东西的前端或未端不能为英文字母阿拉伯字数字或下横线。

1
2
var  str =   "12w-eefd&efrew"  ;  
alert(str.match(/\b\w+\b/g))  //12w,eefd,efrew
实例属性 描述
global 是当前表达式模式首次匹配内容的开始位置，从0开始计数。其初始值为-1，每次成功匹配时，index属性都会随之改变。
ignoreCase 返回创建RegExp对象实例时指定的ignoreCase标志（i）的状态。如果创建RegExp对象实例时设置了i标志，该属性返回True，否则返回False，默认值为False。
lastIndex 是当前表达式模式首次匹配内容中最后一个字符的下一个位置，从0开始计数，常被作为继续搜索时的起始位置，初始值为-1， 表示从起始位置开始搜索，每次成功匹配时，lastIndex属性值都会随之改变。(只有使用exec()或test()方法才会填入，否则为0)
multiLine 返回创建RegExp对象实例时指定的multiLine标志（m）的状态。如果创建RegExp对象实例时设置了m标志，该属性返回True，否则返回False，默认值为False。
source 返回创建RegExp对象实例时指定的表达式文本字符串。 
1
2
3
4
5
6
7
8
9
10
var  str =   "JS's Louvre"  ;  
var  reg = /\w/g; 
alert(reg.exec(str));  //J  
alert(reg.lastIndex);  //1  
alert(reg.exec(str));  //S  
alert(reg.lastIndex);  //2  
alert(reg.exec(str));  //s  
alert(reg.lastIndex);  //4  
alert(reg.exec(str));  //L  
alert(reg.lastIndex);  //6

四、JavaScript字符串应用

4.1 回数

对称数即一个数倒序时，和原数值一样。例如：11，22，111等。

现在利用所学js知识写一个取某范围内所有对称数的函数。

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
function reverseToNum(num){ //将该数值反转，取其反转后的值
    	'use strice';
    	var num = num;
    	var str = num.toString().split("");
    	var reverseStr = str.reverse().join("");
    	var reverseNum = Number(reverseStr);
    	return reverseNum;
    }
    
   	function isReverse(num){//判断该数值是否为对称数
    	'use strice';
    	var num = num;
    	if(num == reverseToNum(num)){
    		return num;
    	}else{
    		return false;
    	}
    }
    
    function countReverse(num){//计算某范围内对称数的总个数，将对称数存入数组并返回
    	'use strice';
		var num = num;
    	var reverseArr = [];
    	if(typeof(num)!='number'){
    		alert("please enter a number");
    		return false;
    	}else if(num<=0){
    		alert("please enter positive integer");
    		return false;
    	}
    	for(var i=1;i<=num;++i){
    		if(isReverse(i)){
    			reverseArr.push(i);
    		}
    	}
    	return reverseArr;
    }

4.2 首字母转化为大写

1
2
3
4
5
6
7
8
9
10
function toUpCase(str){
	'use strict'
	var str = str;
	var strArr = str.split(' ');
	for(var i=0;i<strArr.length;++i){
		strArr[i] = strArr[i].charAt(0).toUpperCase() + strArr[i].slice(1);
	}
	return strArr.join('');
}

Tips: Please indicate the source and original author when reprinting or quoting this article.

特色标签
JavaScript 算法
链友
ESC