-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathleetcode-string.html
557 lines (555 loc) · 172 KB
/
leetcode-string.html
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YQSYM.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/42bab566f107b9a16542343e0368fb77.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0xvg.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/e5221f7d85b0900837a45fb933fa34ec.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YSj7p.jpg" as="image" fetchpriority="high"><meta name="keywords" content="双指针,"><link rel="canonical" href="https://jiankychen.github.io/leetcode-string"><title>LeetCode - 字符串专题</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">LeetCode - 字符串专题</h1><div class="meta"><span class="item" title="创建时间：2022-05-10 14:36:11"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-05-10T14:36:11+08:00">2022-05-10</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>21k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>19 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YQSYM.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/42bab566f107b9a16542343e0368fb77.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0xvg.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/e5221f7d85b0900837a45fb933fa34ec.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YSj7p.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Coding/" itemprop="item" rel="index" title="分类于Coding"><span itemprop="name">Coding<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/leetcode-string.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><h1 id="leetcode-151-颠倒字符串中的单词"><a class="anchor" href="#leetcode-151-颠倒字符串中的单词">#</a> LeetCode 151. 颠倒字符串中的单词</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/reverse-words-in-a-string/">LeetCode 151. Reverse Words in a String</a></p>
<p>给你一个字符串 <code>s</code> ，请你反转字符串中 <strong>单词</strong> 的顺序。</p>
<p><strong>单词</strong> 是由非空格字符组成的字符串。 <code>s</code> 中使用至少一个空格将字符串中的 <strong>单词</strong> 分隔开。</p>
<p>返回 <strong>单词</strong> 顺序颠倒且 <strong>单词</strong> 之间用单个空格连接的结果字符串。</p>
<p><strong>注意</strong>：输入字符串 <code>s</code> 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。</p>
<p>示例 1：</p>
<pre><code>输入：s = "the sky is blue"
输出："blue is sky the"
</code></pre>
<p>示例 2：</p>
<pre><code>输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格
</code></pre>
<p>示例 3：</p>
<pre><code>输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个
</code></pre>
<p></p>
<p>提示：</p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s</code> 包含英文大小写字母、数字和空格 <code>' '</code></li>
<li><code>s</code> 中 至少存在一个 单词</li>
</ul>
<p><strong>进阶</strong>： 如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 额外空间复杂度的 <strong>原地</strong> 解法。</p>
<h2 id="method-1-双指针"><a class="anchor" href="#method-1-双指针">#</a> Method 1: 双指针</h2>
<h2 id="算法思路"><a class="anchor" href="#算法思路">#</a> 算法思路</h2>
<ol>
<li>
<p>移除字符串中多余的空格，包括字符串首部和尾部的空格以及单词之间的多个空格</p>
</li>
<li>
<p>翻转整个字符串</p>
</li>
<li>
<p>逐个翻转每个单词</p>
</li>
</ol>
<p>以 "a good example" 为例：</p>
<ul>
<li>移除多余空格："a good example"</li>
<li>翻转字符串："elpmaxe doog a"</li>
<li>翻转单词："example good a"</li>
</ul>
<p>可参考</p>
<ul>
<li>LeetCode 27. 移除元素</li>
<li>LeetCode 344. 反转字符串</li>
<li>LeetCode 557. 反转字符串中的单词 III</li>
</ul>
<h2 id="算法流程"><a class="anchor" href="#算法流程">#</a> 算法流程</h2>
<ol>
<li>
<p>去除多余空格</p>
<ul>
<li>定义快慢指针 <code>fast</code> 和 <code>slow</code> ， <code>slow</code> 指向 <code>0</code> ， <code>fast</code> 指向从左往右的第一个非空格字符</li>
<li>将 <code>s[fast]</code> 赋给 <code>s[slow]</code> ，然后移动 <code>fast</code> 和 <code>slow</code> 指针，重复该过程，特别地，如果 <code>fast</code> 遇到连续的多个空格，只需将一个空格赋给 <code>s[left]</code></li>
<li>当 <code>fast</code> 移动到字符串的尾后时， <code>slow</code> 指向的是原字符串的最后一个字符。如果 <code>s[slow]</code> 是空字符，将 <code>slow</code> 指针向左移动，直到 <code>slow</code> 指向非空字符</li>
</ul>
</li>
<li>
<p>调整字符串 <code>s</code> 的长度：上一步中的 <code>slow</code> 指向最后一个有效字符，故，有效字符串的长度为 <code>slow + 1</code></p>
</li>
<li>
<p>翻转整个字符串</p>
<ul>
<li>定义 <code>reverse</code> 函数，实现左右指针 <code>left</code> 和 <code>right</code> 之间所有字符的翻转：交换 <code>s[left]</code> 与 <code>s[right]</code> ，并将 <code>left</code> 向右移动、将 <code>right</code> 向左移动</li>
</ul>
</li>
<li>
<p>翻转字符串中的每个单词</p>
<ul>
<li>定义 <code>start</code> 和 <code>end</code> 指针， <code>start</code> 指向单词的起始位置，当 <code>end</code> 指向单词后的空格时或者指向字符串的尾后时，调用 <code>reverse</code> 函数翻转 <code>start</code> 到 <code>end - 1</code> 之间的字符</li>
</ul>
</li>
</ol>
<h2 id="代码实现"><a class="anchor" href="#代码实现">#</a> 代码实现</h2>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 将 left 到 right 之间的所有字符反转</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">void</span> <span class="token function">reverse</span><span class="token punctuation">(</span>string <span class="token operator">&</span>s<span class="token punctuation">,</span> <span class="token keyword">int</span> left<span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator"><</span> right<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token function">swap</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>left<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="6"></td><td><pre></pre></td></tr><tr><td data-num="7"></td><td><pre><span class="token comment">// 双指针，去掉多余空格</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token keyword">void</span> <span class="token function">removeExtraSpaces</span><span class="token punctuation">(</span>string <span class="token operator">&</span>s<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 双指针法</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">int</span> slow <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> fast <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>fast <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>fast<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span><span class="token punctuation">)</span> fast<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token comment">// 跳过字符串首部的空格</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token punctuation">;</span> fast <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> fast<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>fast<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>fast <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span><span class="token punctuation">)</span> <span class="token comment">// 跳过重复的空格</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">continue</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> s<span class="token punctuation">[</span>slow<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> s<span class="token punctuation">[</span>fast<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 移动元素</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="16"></td><td><pre> slow<span class="token operator">--</span><span class="token punctuation">;</span> <span class="token comment">//slow 指向元素移动后的末尾字符</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>slow<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span><span class="token punctuation">)</span> slow<span class="token operator">--</span><span class="token punctuation">;</span> <span class="token comment">//slow 移到最后一个非空格字符的位置（排除字符串尾部的空格）</span></pre></td></tr><tr><td data-num="18"></td><td><pre> s<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>slow <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 调整 s 的大小</span></pre></td></tr><tr><td data-num="19"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="20"></td><td><pre></pre></td></tr><tr><td data-num="21"></td><td><pre><span class="token comment">// 翻转字符串中的单词</span></pre></td></tr><tr><td data-num="22"></td><td><pre>string <span class="token function">reverseWords</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token function">removeExtraSpaces</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 移除多余空格</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 反转整个字符串</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">int</span> start <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> end <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>end <span class="token operator"><=</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 双指针法，反转每个单词</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>end<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span> <span class="token operator">||</span> end <span class="token operator">==</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//end 遇到空格或者到达尾后，反转单词</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> start<span class="token punctuation">,</span> end <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="29"></td><td><pre> start <span class="token operator">=</span> end <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 下一个单词的起点</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="31"></td><td><pre> end<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="32"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token keyword">return</span> s<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="34"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><h2 id="复杂度分析"><a class="anchor" href="#复杂度分析">#</a> 复杂度分析</h2>
<p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<blockquote>
<p>有关 多余空格的去除 ，还可以参考 <a target="_blank" rel="noopener" href="https://www.programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html">代码随想录：翻转字符串里的单词</a> 中的思路</p>
</blockquote>
<h2 id="method-2-一次遍历"><a class="anchor" href="#method-2-一次遍历">#</a> Method 2: 一次遍历</h2>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">reverseWords</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 反转整个字符串（库函数）</span></pre></td></tr><tr><td data-num="3"></td><td><pre></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> start <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> start <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>start<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//start 用于寻找每个单词的第一个字母</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>start<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token char">' '</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遇到单词的第一个字母</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> s<span class="token punctuation">[</span>index<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">' '</span><span class="token punctuation">;</span> <span class="token comment">// 添加空格，然后将 index 移动到下一个单词的开头位置</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">int</span> end <span class="token operator">=</span> start<span class="token punctuation">;</span> <span class="token comment">// 单词的最后一个字母</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>end <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>end<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token char">' '</span><span class="token punctuation">)</span> s<span class="token punctuation">[</span>index<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> s<span class="token punctuation">[</span>end<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 寻找单词的最后一个字母</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">+</span> index <span class="token operator">-</span> <span class="token punctuation">(</span>end <span class="token operator">-</span> start<span class="token punctuation">)</span><span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">+</span> index<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 反转整个单词</span></pre></td></tr><tr><td data-num="11"></td><td><pre> start <span class="token operator">=</span> end<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> s<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 修改字符串 s 的长度（提取有效字符）</span></pre></td></tr><tr><td data-num="15"></td><td><pre></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">return</span> s<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>参考：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/reverse-words-in-a-string/solution/fan-zhuan-zi-fu-chuan-li-de-dan-ci-by-leetcode-sol/">leetcode-solution</a></p>
<h1 id="leetcode-208-实现-trie-前缀树"><a class="anchor" href="#leetcode-208-实现-trie-前缀树">#</a> LeetCode 208. 实现 Trie (前缀树)</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-trie-prefix-tree/">208. Implement Trie (Prefix Tree)</a></p>
<p><strong>Trie</strong>（发音类似 "try"）或者说 <strong>前缀树</strong> 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。</p>
<p>请你实现 <code>Trie</code> 类：</p>
<ul>
<li><code>Trie()</code> 初始化前缀树对象。</li>
<li><code>void insert(String word)</code> 向前缀树中插入字符串 <code>word</code> 。</li>
<li><code>boolean search(String word)</code> 如果字符串 <code>word</code> 在前缀树中，返回 <code>true</code> （即，在检索之前已经插入）；否则，返回 <code>false</code> 。</li>
<li><code>boolean startsWith(String prefix)</code> 如果之前已经插入的字符串 <code>word</code> 的前缀之一为 <code>prefix</code> ，返回 <code>true</code> ；否则，返回 <code>false</code> 。</li>
</ul>
<p><strong>示例：</strong></p>
<pre><code>输入:
["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
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>word.length</code> , <code>prefix.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>2000</mn></mrow><annotation encoding="application/x-tex">\le 2000</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2000</span></span></span></span></li>
<li><code>word</code> 和 <code>prefix</code> 仅由小写英文字母组成</li>
<li><code>insert</code> 、 <code>search</code> 和 <code>startsWith</code> 调用次数 总计 不超过 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">3 \times 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">3</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span> 次</li>
</ul>
<h2 id="思路"><a class="anchor" href="#思路">#</a> 思路</h2>
<p>Trie 又称前缀树或字典树，是一种用于快速查询 某个字符串 / 字符前缀 是否存在的数据结构</p>
<p>Trie 的每个节点包含以下字段：</p>
<ul>
<li>指向子节点的指针数组 children</li>
<li>布尔字段 isEnd，表示该节点是否为字符串的结尾</li>
</ul>
<p>例如：<br>
<img loading="lazy" data-src="LeetCode-%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%93%E9%A2%98/LeetCode208_Example.webp" alt=""></p>
<h2 id="method-字典树"><a class="anchor" href="#method-字典树">#</a> Method: 字典树</h2>
<p>算法思路：</p>
<p>本题的 children 数组的长度为 26，即小写英文字母的数量，其中，children [0] 对应 a，children [25] 对应 z</p>
<p>定义函数 Trie* searchPrefix (string prefix) 用于判断字典树是否存在前缀 prefix ：若搜索到了前缀的末尾，就说明字典树中存在该前缀，否则，字典树不存在该前缀</p>
<p>特别地，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">Trie</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">private</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="3"></td><td><pre> Trie<span class="token operator">*</span> children<span class="token punctuation">[</span><span class="token number">26</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">bool</span> isEnd<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre></pre></td></tr><tr><td data-num="6"></td><td><pre> Trie<span class="token operator">*</span> <span class="token function">searchPrefix</span><span class="token punctuation">(</span>string prefix<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 判断字典树是否存在前缀 prefix</span></pre></td></tr><tr><td data-num="7"></td><td><pre> Trie<span class="token operator">*</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> prefix<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">int</span> tmp <span class="token operator">=</span> c <span class="token operator">-</span> <span class="token char">'a'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-></span>children<span class="token punctuation">[</span>tmp<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token keyword">nullptr</span><span class="token punctuation">)</span> <span class="token comment">// 不存在 prefix，返回空指针</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">return</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> node <span class="token operator">=</span> node<span class="token operator">-></span>children<span class="token punctuation">[</span>tmp<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">return</span> node<span class="token punctuation">;</span> <span class="token comment">// 存在 prefix，则返回末尾指针</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="16"></td><td><pre></pre></td></tr><tr><td data-num="17"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token function">Trie</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="19"></td><td><pre> isEnd <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token number">26</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="21"></td><td><pre> children<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="23"></td><td><pre></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token operator">~</span><span class="token function">Trie</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 析构函数，避免内存泄漏</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token number">26</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>children<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token keyword">nullptr</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">delete</span> children<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="30"></td><td><pre> </pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token keyword">void</span> <span class="token function">insert</span><span class="token punctuation">(</span>string word<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 插入字符串 word</span></pre></td></tr><tr><td data-num="32"></td><td><pre> Trie<span class="token operator">*</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> word<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="34"></td><td><pre> <span class="token keyword">int</span> tmp <span class="token operator">=</span> c <span class="token operator">-</span> <span class="token char">'a'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="35"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-></span>children<span class="token punctuation">[</span>tmp<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token keyword">nullptr</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="36"></td><td><pre> node<span class="token operator">-></span>children<span class="token punctuation">[</span>tmp<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Trie</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="37"></td><td><pre> node <span class="token operator">=</span> node<span class="token operator">-></span>children<span class="token punctuation">[</span>tmp<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="38"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="39"></td><td><pre> node<span class="token operator">-></span>isEnd <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="40"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="41"></td><td><pre> </pre></td></tr><tr><td data-num="42"></td><td><pre> <span class="token keyword">bool</span> <span class="token function">search</span><span class="token punctuation">(</span>string word<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 判断字符串 word 是否存在</span></pre></td></tr><tr><td data-num="43"></td><td><pre> Trie<span class="token operator">*</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token operator">-></span><span class="token function">searchPrefix</span><span class="token punctuation">(</span>word<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="44"></td><td><pre> <span class="token keyword">return</span> node <span class="token operator">!=</span> <span class="token keyword">nullptr</span> <span class="token operator">&&</span> node<span class="token operator">-></span>isEnd<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="45"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="46"></td><td><pre> </pre></td></tr><tr><td data-num="47"></td><td><pre> <span class="token keyword">bool</span> <span class="token function">startsWith</span><span class="token punctuation">(</span>string prefix<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 判断前缀 prefix 是否存在</span></pre></td></tr><tr><td data-num="48"></td><td><pre> <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-></span><span class="token function">searchPrefix</span><span class="token punctuation">(</span>prefix<span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="49"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="50"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="51"></td><td><pre></pre></td></tr><tr><td data-num="52"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="53"></td><td><pre> * Your Trie object will be instantiated and called as such:</pre></td></tr><tr><td data-num="54"></td><td><pre> * Trie* obj = new Trie();</pre></td></tr><tr><td data-num="55"></td><td><pre> * obj->insert(word);</pre></td></tr><tr><td data-num="56"></td><td><pre> * bool param_2 = obj->search(word);</pre></td></tr><tr><td data-num="57"></td><td><pre> * bool param_3 = obj->startsWith(prefix);</pre></td></tr><tr><td data-num="58"></td><td><pre> */</pre></td></tr></tbody></table></figure><p>时间复杂度：初始化所需时间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，其余操作所需时间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\vert S \vert)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.05764em;">S</span><span class="mord">∣</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert S \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.05764em;">S</span><span class="mord">∣</span></span></span></span> 是每次插入或查询的字符串的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi mathvariant="normal">∣</mi><mi>T</mi><mi mathvariant="normal">∣</mi><mo>⋅</mo><mi mathvariant="normal">∣</mi><mi mathvariant="normal">Σ</mi><mi mathvariant="normal">∣</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\vert T \vert \cdot \vert \Sigma \vert)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.13889em;">T</span><span class="mord">∣</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣Σ∣</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi>T</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert T \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.13889em;">T</span><span class="mord">∣</span></span></span></span> 是插入字典树中的所有字符串的长度之和，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi mathvariant="normal">Σ</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert \Sigma \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣Σ∣</span></span></span></span> 是字符集的大小（本题 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi mathvariant="normal">Σ</mi><mi mathvariant="normal">∣</mi><mo>=</mo><mn>26</mn></mrow><annotation encoding="application/x-tex">\vert \Sigma \vert = 26</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣Σ∣</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">26</span></span></span></span>）</p>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/">leetcode-solution</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/">宫水三叶</a></li>
</ul>
<h1 id="leetcode-28-实现-strstr"><a class="anchor" href="#leetcode-28-实现-strstr">#</a> LeetCode 28. 实现 strStr ()</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-strstr/">LeetCode 28. Implement strStr()</a></p>
<p>给你两个字符串 <code>haystack</code> 和 <code>needle</code> ，请你在 <code>haystack</code> 字符串中找出 <code>needle</code> 字符串的第一个匹配项的下标（下标从 0 开始）。如果 <code>needle</code> 不是 <code>haystack</code> 的一部分，则返回 -1 。</p>
<p><strong>Clarification:</strong></p>
<ul>
<li>
<p>当 <code>needle</code> 是一个空字符串时，我们应该返回什么？</p>
</li>
<li>
<p>当 <code>needle</code> 是空字符串时，我们将返回 0。这与 C 语言的 <code>strstr()</code> 和 Java 的 <code>indexOf()</code> 一致。</p>
</li>
</ul>
<p></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：haystack = "hello", needle = "ll"
输出：2
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：haystack = "aaaaa", needle = "bba"
输出：-1
</code></pre>
<p></p>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>haystack.length</code> , <code>needle.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>haystack</code> and <code>needle</code> consist of only lowercase English characters.</li>
</ul>
<h2 id="思路-2"><a class="anchor" href="#思路-2">#</a> 思路</h2>
<p>本题是经典的字符串单模匹配的模型，可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/">力扣官方题解：实现 strStr ()</a></p>
<h2 id="method-1-暴力搜索"><a class="anchor" href="#method-1-暴力搜索">#</a> Method 1: 暴力搜索</h2>
<p>基本思路：让字符串 <code>needle</code> 与字符串 <code>haystack</code> 中所有长度为 <code>m</code> 的子串均匹配一次，其中， <code>m</code> 为字符串 <code>needle</code> 的长度</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 检查字符串 haystack 中以索引 start 开头的一连串字符是否与 needle 字符串匹配</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">bool</span> <span class="token function">isSubStr</span><span class="token punctuation">(</span>string haystack<span class="token punctuation">,</span> <span class="token keyword">int</span> start<span class="token punctuation">,</span> string needle<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> needle<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>haystack<span class="token punctuation">[</span>start<span class="token punctuation">]</span> <span class="token operator">!=</span> c<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> start<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token keyword">int</span> <span class="token function">strStr</span><span class="token punctuation">(</span>string haystack<span class="token punctuation">,</span> string needle<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> haystack<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isSubStr</span><span class="token punctuation">(</span>haystack<span class="token punctuation">,</span> i<span class="token punctuation">,</span> needle<span class="token punctuation">)</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">return</span> i<span class="token punctuation">;</span> </pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>×</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \times m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为字符串 <code>haystack</code> 的长度，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 为字符串 <code>needle</code> 的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<h2 id="method-2-kmp-算法"><a class="anchor" href="#method-2-kmp-算法">#</a> Method 2: KMP 算法</h2>
<p>文本串为 <code>haystack</code> ，模式串为 <code>needle</code> ，利用 KMP 算法进行字符串匹配</p>
<p>算法流程：</p>
<ol>
<li>
<p>构造 next 数组，用于查找回退位置</p>
</li>
<li>
<p>利用 next 数组进行匹配，定义 <code>i</code> 为文本串索引， <code>j</code> 为模式串索引，执行循环：</p>
<ul>
<li>若模式串字符 <code>needle[j]</code> 与文本串字符 <code>haystack[i]</code> 相同，则将 <code>i</code> 和 <code>j</code> 同时右移</li>
<li>若不相同，连续执行 <code>j = next[j - 1]</code> ，直到 <code>needle[j] == haystack[i]</code> 或 <code>j == 0</code></li>
</ul>
</li>
</ol>
<p>具体原理及步骤可参阅 <a href="https://jiankychen.github.io/posts/36b55f59/">KMP 算法</a></p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 计算 next 数组</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">void</span> <span class="token function">getNext</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>next<span class="token punctuation">,</span> string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> prefix <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> next<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> suffix <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> suffix <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> suffix<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>prefix <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>prefix<span class="token punctuation">]</span> <span class="token operator">!=</span> s<span class="token punctuation">[</span>suffix<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="7"></td><td><pre> prefix <span class="token operator">=</span> next<span class="token punctuation">[</span>prefix <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>prefix<span class="token punctuation">]</span> <span class="token operator">==</span> s<span class="token punctuation">[</span>suffix<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="9"></td><td><pre> prefix<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> next<span class="token punctuation">[</span>suffix<span class="token punctuation">]</span> <span class="token operator">=</span> prefix<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre></pre></td></tr><tr><td data-num="14"></td><td><pre><span class="token comment">// 字符串匹配</span></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token keyword">int</span> <span class="token function">strStr</span><span class="token punctuation">(</span>string haystack<span class="token punctuation">,</span> string needle<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="16"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">next</span><span class="token punctuation">(</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token function">getNext</span><span class="token punctuation">(</span>next<span class="token punctuation">,</span> needle<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> haystack<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>j <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&&</span> needle<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">!=</span> haystack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token comment">//needle [j] 与 haystack [i] 不同，回退 j</span></pre></td></tr><tr><td data-num="21"></td><td><pre> j <span class="token operator">=</span> next<span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>needle<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> haystack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token comment">//needle [j] 与 haystack [i] 相同，右移 i 和 j</span></pre></td></tr><tr><td data-num="23"></td><td><pre> j<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token comment">// 匹配完成</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">return</span> <span class="token punctuation">(</span>i <span class="token operator">-</span> needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 正确匹配的起点索引为 i - needle.size () + 1</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n + m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，使用额外空间存储 next 数组</p>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://www.programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html">代码随想录</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/">力扣官方题解</a></li>
</ul>
<h1 id="leetcode-344-反转字符串"><a class="anchor" href="#leetcode-344-反转字符串">#</a> LeetCode 344. 反转字符串</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-string/">LeetCode 344. Reverse String</a></p>
<p>编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 <code>s</code> 的形式给出。</p>
<p>不要给另外的数组分配额外的空间，你必须<strong>原地修改</strong>输入数组、使用 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 的额外空间解决这一问题。</p>
<p></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s[i]</code> 都是 ASCII 码表中的可打印字符</li>
</ul>
<h2 id="method-双指针"><a class="anchor" href="#method-双指针">#</a> Method: 双指针</h2>
<p>解题步骤：</p>
<ol>
<li>定义 <code>left</code> 指向字符数组首元素， <code>right</code> 指向字符数组尾元素</li>
<li>当 <code>left < right</code> 时，执行循环：交换 <code>s[left]</code> 和 <code>s[right]</code> ， <code>left</code> 指针右移一位； <code>right</code> 指针左移一位</li>
</ol>
<p>代码如下：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">void</span> <span class="token function">reverseString</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">char</span><span class="token operator">></span><span class="token operator">&</span> s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> left <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> right <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 双指针</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator"><</span> right<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token function">swap</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>left<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 交换，并移动指针</span></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span></span></span></span> 为字符数组的长度，一共执行了 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi><mi mathvariant="normal">/</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">N/2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mord">/2</span></span></span></span> 次的交换</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<p>如果库函数仅仅是解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数，例如这里使用的 <code>swap</code> 函数</p>
<p><code>swap</code> 函数具有两种实现方式，以交换 <code>s[left]</code> 和 <code>s[right]</code> 为例：</p>
<ol>
<li>
<p>直接交换数值</p>
<pre><code> int temp = s[left]; // 中间量
s[left] = s[right];
s[right] = temp;
</code></pre>
</li>
<li>
<p>位运算（异或）</p>
<pre><code> s[left] ^= s[right]; // 中间量
s[right] ^= s[left]; // 将中间量与 s[right] 进行异或运算， = 号右边得到的是原始的 s[left]
s[left] ^= s[right]; // 将中间量与 s[right] （即原始的 s[left] ） 进行异或运算， = 号右边得到的是原始的 s[right]
</code></pre>
</li>
</ol>
<h1 id="leetcode-459-重复的子字符串"><a class="anchor" href="#leetcode-459-重复的子字符串">#</a> LeetCode 459. 重复的子字符串</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/repeated-substring-pattern/">LeetCode 459. Repeated Substring Pattern</a></p>
<p>给定一个非空的字符串 <code>s</code> ，检查是否可以通过由它的一个子串重复多次构成。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "abab"
输出：true
解释：可由子串 "ab" 重复两次构成
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "aba"
输出：false
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：s = "abcabcabcabc"
输出：true
解释：可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s</code> 由小写英文字母组成</li>
</ul>
<h2 id="思路-3"><a class="anchor" href="#思路-3">#</a> 思路</h2>
<p>检查字符串是否由重复的子串组成，即，验证字符串 <code>s</code> 的周期性</p>
<p>可以通过构造 next 数组，获取字符串 <code>s</code> 的周期信息</p>
<p>next 数组最后一位元素记录了整个字符串的 最长相同前后缀 的长度，记作 <code>next[s.size() - 1]</code> 。若字符串具有周期性， <code>next[s.size() - 1]</code> 就应该是周期的整数倍，且应该是 <em>字符串的总周期数 - 1</em> 倍。换而言之， <code>s.size() - next[s.size() - 1]</code> 就是周期的长度</p>
<p>有关 next 数组及其构造，可参阅 <a href="https://jiankychen.github.io/posts/36b55f59/">KMP 算法</a></p>
<p>以字符串 "abcabcabc" 为例，其 next 数组为：</p>
<table>
<thead>
<tr>
<th style="text-align:center">下标</th>
<th style="text-align:center">0</th>
<th style="text-align:center">1</th>
<th style="text-align:center">2</th>
<th style="text-align:center">3</th>
<th style="text-align:center">4</th>
<th style="text-align:center">5</th>
<th style="text-align:center">6</th>
<th style="text-align:center">7</th>
<th style="text-align:center">8</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">字符串</td>
<td style="text-align:center">a</td>
<td style="text-align:center">b</td>
<td style="text-align:center">c</td>
<td style="text-align:center">a</td>
<td style="text-align:center">b</td>
<td style="text-align:center">c</td>
<td style="text-align:center">a</td>
<td style="text-align:center">b</td>
<td style="text-align:center">c</td>
</tr>
<tr>
<td style="text-align:center">next 数组</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">2</td>
<td style="text-align:center">3</td>
<td style="text-align:center">4</td>
<td style="text-align:center">5</td>
<td style="text-align:center">6</td>
</tr>
</tbody>
</table>
<p>其周期长度 = 字符串总长度 - next 数组最后一位元素值 = 9 - 6 = 3</p>
<p>因此，可以作出以下结论：若 <strong> <code>next[s.size() - 1]</code> 非零</strong> 且 <strong>字符串总长度 <code>s.size()</code> 能够被 <code>s.size() - next[s.size() - 1]</code> 整除</strong> ，则，字符串具有周期性，即，可以由子串重复多次而构成</p>
<p>有关该方法正确性的理论证明，可参考 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/">力扣官方题解：重复的子字符串（方法三）</a></p>
<h2 id="methodkmp-算法"><a class="anchor" href="#methodkmp-算法">#</a> Method：KMP 算法</h2>
<p>解题流程：</p>
<ol>
<li>构造 next 数组</li>
<li>找到 next 数组最后一位元素，即， <code>next[s.size() - 1]</code></li>
<li>判断 <code>next[s.size() - 1]</code> 是否为 0
<ul>
<li>若 <code>next[s.size() - 1] == 0</code> ，字符串不存在周期， <code>return false</code></li>
<li>若 <code>next[s.size() - 1] != 0</code> ，判断 <code>s.size()</code> 是否能被 <code>s.size() - next[s.size() - 1]</code> 整除
<ul>
<li>若能够被整除，字符串具有周期性， <code>return true</code></li>
<li>若不能被整除， <code>return false</code></li>
</ul>
</li>
</ul>
</li>
</ol>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 构造 next 数组</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">void</span> <span class="token function">getNext</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>next<span class="token punctuation">,</span> string s<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 注意，要对 next 加引用符 &</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> prefix <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> next<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> suffix <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> suffix <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> suffix<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>prefix <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>prefix<span class="token punctuation">]</span> <span class="token operator">!=</span> s<span class="token punctuation">[</span>suffix<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="7"></td><td><pre> prefix <span class="token operator">=</span> next<span class="token punctuation">[</span>prefix <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>prefix<span class="token punctuation">]</span> <span class="token operator">==</span> s<span class="token punctuation">[</span>suffix<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="9"></td><td><pre> prefix<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> next<span class="token punctuation">[</span>suffix<span class="token punctuation">]</span> <span class="token operator">=</span> prefix<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre></pre></td></tr><tr><td data-num="14"></td><td><pre><span class="token keyword">bool</span> <span class="token function">repeatedSubstringPattern</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="15"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">next</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token function">getNext</span><span class="token punctuation">(</span>next<span class="token punctuation">,</span> s<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token comment">//for (auto c : next) // 打印 next 数组</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token comment">// cout << c << " ";</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token comment">// cout << endl;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">int</span> temp <span class="token operator">=</span> next<span class="token punctuation">[</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>temp <span class="token operator">!=</span> <span class="token number">0</span> <span class="token operator">&&</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> temp<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是字符串 <code>s</code> 的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<blockquote>
<p>可以通过打印 next 数组来检查 next 数组的构造是否正确，并帮助理解做题思路</p>
</blockquote>
<h1 id="leetcode-541-反转字符串-ii"><a class="anchor" href="#leetcode-541-反转字符串-ii">#</a> LeetCode 541. 反转字符串 II</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-string-ii/">LeetCode 541. Reverse String II</a></p>
<p>给定一个字符串 <code>s</code> 和一个整数 <code>k</code> ，从字符串开头算起，每计数至 <code>2k</code> 个字符，就反转这 <code>2k</code> 字符中的前 <code>k</code> 个字符。</p>
<ul>
<li>如果剩余字符少于 <code>k</code> 个，则将剩余字符全部反转。</li>
<li>如果剩余字符小于 <code>2k</code> 但大于或等于 <code>k</code> 个，则反转前 <code>k</code> 个字符，其余字符保持原样。</li>
</ul>
<p></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "abcdefg", k = 2
输出："bacdfeg"
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "abcd", k = 2
输出："bacd"
</code></pre>
<p></p>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s</code> 仅由小写英文组成</li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>k</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
</ul>
<h2 id="思路-4"><a class="anchor" href="#思路-4">#</a> 思路</h2>
<p>直接按题意进行模拟：</p>
<p>反转每个下标从 <code>2k</code> 的倍数开始的、长度为 <code>k</code> 的子串，若该子串长度不足 <code>k</code> ，则反转整个子串</p>
<h2 id="method-双指针-2"><a class="anchor" href="#method-双指针-2">#</a> Method: 双指针</h2>
<p>解题步骤：</p>
<p>将字符串 <code>s</code> 分成若干段长为 <code>2k</code> 的区间（最后一段不足 <code>2k</code> 也同样视为一个区间），针对每个区间执行以下操作</p>
<ul>
<li>若区间内的字符多于 <code>k</code> 个，反转前 <code>k</code> 个字符，反转操作与 LeetCode 344. 反转字符串 一致</li>
<li>若区间内的字符少于 <code>k</code> 个，反转所有字符</li>
</ul>
<p>其中，针对区间的遍历，只需遍历区间的起点，即，以 <code>i = 0</code> 为起点，每次按照 <code>i = i + 2 * k</code> 更新 <code>i</code> ，当 <code>i >= s.size()</code> 时结束遍历</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 反转 left 到 right 之间的字符</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">void</span> <span class="token function">reverse</span><span class="token punctuation">(</span>string <span class="token operator">&</span>s<span class="token punctuation">,</span> <span class="token keyword">int</span> left<span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator"><</span> right<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token function">swap</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>left<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="6"></td><td><pre></pre></td></tr><tr><td data-num="7"></td><td><pre><span class="token comment">// 反转字符串</span></pre></td></tr><tr><td data-num="8"></td><td><pre>string <span class="token function">reverseStr</span><span class="token punctuation">(</span>string s<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i <span class="token operator">+=</span> <span class="token number">2</span> <span class="token operator">*</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 每 2k 个字符，进行一次 前 k 个字符的反转</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">+</span> k <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 剩余字符多于 k 个，反转前 k 个字符</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> i<span class="token punctuation">,</span> i <span class="token operator">+</span> k <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">continue</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> i<span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 剩余字符少于 k 个，将全部剩余字符反转</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">return</span> s<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>特别地，可以将上述 <code>for</code> 循环写成：</p>
<pre><code>for (int i = 0; i < s.size(); i += 2 * k)
reverse(s, i, min(i + k - 1, num.size() - 1));
</code></pre>
<p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为字符串长度</p>
<ul>
<li>遍历 <code>i</code> 的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi mathvariant="normal">/</mi><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n / k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mord">/</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span></li>
<li>每反转 <code>k</code> 个字符的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<blockquote>
<p>当需要以固定规律对字符串逐段处理时，可试着在 <code>for</code> 循环的表达式上做做文章</p>
</blockquote>
<p>参考：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-string-ii/solution/fan-zhuan-zi-fu-chuan-ii-by-leetcode-sol-ua7s/">力扣官方题解：反转字符串 II</a></p>
<h1 id="leetcode-557-反转字符串中的单词-iii"><a class="anchor" href="#leetcode-557-反转字符串中的单词-iii">#</a> LeetCode 557. 反转字符串中的单词 III</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/">LeetCode 557</a></p>
<p>给定一个字符串 <code>s</code> ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。</p>
<p></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "God Ding"
输出："doG gniD"
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>5</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 5 \times 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">5</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s</code> 包含可打印的 ASCII 字符</li>
<li><code>s</code> 不包含任何开头或结尾空格</li>
<li><code>s</code> 里 至少 有一个词</li>
<li><code>s</code> 中的所有单词都用一个空格隔开</li>
<li></li>
</ul>
<h2 id="method-1-双指针原地解法"><a class="anchor" href="#method-1-双指针原地解法">#</a> Method 1: 双指针（原地解法）</h2>
<p>当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符…… 如此反复，就可以在原空间上翻转单词。</p>
<p>具体流程如下：</p>
<ol>
<li>指针 <code>left</code> 指向第一个字符或空字符前一个字符（双指针中的左端指针）</li>
<li>指针 <code>search</code> 向右搜索</li>
<li>当 <code>search</code> 搜索到空字符或尾后时，将 <code>search - 1</code> 赋给双指针中的右端指针 <code>right</code></li>
<li>将 <code>left</code> 和 <code>right</code> 之间的所有字符反转</li>
</ol>
<p>重复上述操作，直到所有字符均已被反转</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">reverseWords</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> search <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">auto</span> n <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>search <span class="token operator"><</span> n<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">int</span> left <span class="token operator">=</span> search<span class="token punctuation">;</span> <span class="token comment">//left 指向第一个字符或空字符后一个字符</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>search<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token char">' '</span> <span class="token operator">&&</span> search <span class="token operator"><</span> n<span class="token punctuation">)</span> <span class="token comment">// 向右搜索，直到遇到空字符或者最后一个字符</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> search<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">int</span> right <span class="token operator">=</span> search <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">//right 指向空字符前一个位置，即，单词最后一个字符所在位置</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator"><</span> right<span class="token punctuation">)</span> <span class="token comment">// 反转单词</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token function">swap</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>left<span class="token punctuation">]</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span>right<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> left<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> right<span class="token operator">--</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> search<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token comment">// 继续搜索</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">return</span> s<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span> ，字符串中的每个字符要么在 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 的时间内被交换到相应的位置，要么因为是空格而保持不动</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> ，因为不需要开辟额外的数组</p>
<h2 id="method-2-双指针使用额外空间"><a class="anchor" href="#method-2-双指针使用额外空间">#</a> Method 2: 双指针（使用额外空间）</h2>
<p>开辟一个新字符串。从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词并得到单词的起止位置。随后，将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串。</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">reverseWords</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> string ret<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> length <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">length</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> length<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">int</span> start <span class="token operator">=</span> i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> length <span class="token operator">&&</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token char">' '</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="8"></td><td><pre> i<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> p <span class="token operator">=</span> start<span class="token punctuation">;</span> p <span class="token operator"><</span> i<span class="token punctuation">;</span> p<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>start <span class="token operator">+</span> i <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">-</span> p<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> length <span class="token operator">&&</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> i<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token char">' '</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">return</span> ret<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span> ，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span></span></span></span> 为字符串的长度。原字符串中的每个字符都会在 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 的时间内放入新字符串中</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span> ，开辟了与原字符串等大的空间</p>
<h1 id="剑指-offer-05-替换空格"><a class="anchor" href="#剑指-offer-05-替换空格">#</a> 剑指 Offer 05. 替换空格</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/">剑指 Offer 05. 替换空格</a></p>
<p>请实现一个函数，把字符串 <code>s</code> 中的每个空格替换成 "<strong>%20</strong>"</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "We are happy."
输出："We%20are%20happy."
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">0 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>10000</mn></mrow><annotation encoding="application/x-tex">\le 10000</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">10000</span></span></span></span></li>
</ul>
<h2 id="method-1-遍历添加"><a class="anchor" href="#method-1-遍历添加">#</a> Method 1: 遍历添加</h2>
<p>遍历字符串 <code>s</code> 中的每个字符，如果不是空格，直接赋值给新字符串；否则，赋值 “%20” 到新字符串</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">replaceSpace</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> string ans <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isspace</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> ans <span class="token operator">+=</span> <span class="token string">"%20"</span><span class="token punctuation">;</span> <span class="token comment">// 等价于 ans.append ("%20")</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">else</span> ans <span class="token operator">+=</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 等价于 ans.push_back (s [i])</span></pre></td></tr><tr><td data-num="7"></td><td><pre> i<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>其中， <code>string</code> 的成员函数：</p>
<ul>
<li>
<p><code>append()</code> ：向后加入的是 <code>string</code> 类型</p>
</li>
<li>
<p><code>push_back()</code> ：向后加入的是 <code>char</code> 类型</p>
</li>
</ul>
<p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为字符串的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，新建了一个字符串</p>
<h2 id="method-2-原地修改双指针"><a class="anchor" href="#method-2-原地修改双指针">#</a> Method 2: 原地修改（双指针）</h2>
<p>基本思路：先统计整个字符串中的空格数目，然后把字符串大小扩充为替换后的大小，用 双指针 方法 <strong>从右向左</strong> 移元素</p>
<p>解题步骤：</p>
<ol>
<li>
<p>统计空格数量 <code>count</code></p>
</li>
<li>
<p>修改 <code>s</code> 长度：将所有空格都替换成 "%20" 后，新字符串应比原字符串长 <code>2 * count</code></p>
</li>
<li>
<p>定义指针 <code>left</code> 指向原字符串尾部元素， <code>right</code> 指向新字符串尾部元素</p>
</li>
<li>
<p>从右向左遍历修改 <code>s</code> ，当 <code>left == right</code> 时（代表左边已没有空格）结束循环</p>
<ul>
<li>
<p>当 <code>s[left]</code> 不是空格时，执行 <code>s[right] = s[left]</code></p>
</li>
<li>
<p>当 <code>s[left]</code> 是空格时，将区间 <code>[right - 2, right]</code> 内的元素修改为 "%20"</p>
</li>
</ul>
</li>
</ol>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">replaceSpace</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token comment">// 统计空格数量</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> s<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token char">' '</span><span class="token punctuation">)</span> count<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token comment">// 扩充字符串长度</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">int</span> oldSize <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> newSize <span class="token operator">=</span> oldSize <span class="token operator">+</span> <span class="token number">2</span> <span class="token operator">*</span> count<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> s<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>newSize<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token comment">// 双指针法</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">int</span> left <span class="token operator">=</span> oldSize <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> right <span class="token operator">=</span> newSize <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator"><</span> right<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>left<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">' '</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="13"></td><td><pre> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">'0'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">'2'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">'%'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> left<span class="token operator">--</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">else</span></pre></td></tr><tr><td data-num="19"></td><td><pre> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span> <span class="token operator">=</span> s<span class="token punctuation">[</span>left<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">return</span> s<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，统计空格数量、双指针法修改 <code>s</code> 的时间复杂度均为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，由于是原地扩展 <code>s</code> 长度，因此使用 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 额外空间</p>
<p>很多数组 / 字符串填充类的问题，都可以预先扩充数组的大小，然后再从右向左进行操作</p>
<p>这样做有两个好处：</p>
<ol>
<li>不用申请新数组，降低了空间复杂度</li>
<li>从右向左填充元素，避免了从左向右填充元素带来的 “每次添加元素都要将该位置右边的元素向后移动” 的问题，既降低了时间复杂度，也简化了算法</li>
</ol>
<p>参考：<a target="_blank" rel="noopener" href="https://www.programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html">代码随想录</a></p>
<h1 id="剑指-offer-58-ii-左旋转字符串"><a class="anchor" href="#剑指-offer-58-ii-左旋转字符串">#</a> 剑指 Offer 58-II. 左旋转字符串</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/">剑指 Offer 58-II. 左旋转字符串</a></p>
<p>字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串 "abcdefg" 和数字 2，该函数将返回左旋转两位得到的结果 "cdefgab"。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "abcdefg", k = 2
输出："cdefgab"
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "lrloseumgh", k = 6
输出："umghlrlose"
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>k</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo></mrow><annotation encoding="application/x-tex">\le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>10000</mn></mrow><annotation encoding="application/x-tex">\le 10000</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">10000</span></span></span></span></li>
</ul>
<p><strong>进阶</strong>：你能想出一个仅使用常数空间的原地操作算法吗？</p>
<h2 id="思路-5"><a class="anchor" href="#思路-5">#</a> 思路</h2>
<p>解题思路：</p>
<ol>
<li>将整个字符串 <code>s</code> 反转</li>
<li>将前 <code>s.size() - n</code> 个字符反转</li>
<li>将后 <code>n</code> 个字符反转</li>
</ol>
<p>以 <code>s = "abcdefg"</code> ， <code>n = 2</code> 为例：</p>
<ul>
<li>反转整个字符串，得到："gfedcba"</li>
<li>反转前 5 个字符串，得到："cdefgba"</li>
<li>反转后 2 个字符串，得到："cdefgab"</li>
</ul>
<h2 id="method-双指针-3"><a class="anchor" href="#method-双指针-3">#</a> Method: 双指针</h2>
<p>采用双指针法实现字符串的反转</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">void</span> <span class="token function">reverse</span><span class="token punctuation">(</span>string <span class="token operator">&</span>s<span class="token punctuation">,</span> <span class="token keyword">int</span> left<span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator"><</span> right<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token function">swap</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>left<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span>right<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="5"></td><td><pre></pre></td></tr><tr><td data-num="6"></td><td><pre>string <span class="token function">reverseLeftWords</span><span class="token punctuation">(</span>string s<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> n<span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">return</span> s<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span></span></span></span> 为字符串长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<div class="tags"><a href="/tags/%E5%8F%8C%E6%8C%87%E9%92%88/" rel="tag"><i class="ic i-tag"></i>双指针</a><a href="/tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" rel="tag"><i class="ic i-tag"></i>字符串</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 23:08:38" itemprop="dateModified" datetime="2024-06-08T23:08:38+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/leetcode-string.html" title="LeetCode - 字符串专题">https://jiankychen.github.io/leetcode-string.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/leetcode-hashtable.html" rel="prev" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/Y0zdB.jpg" title="LeetCode - 哈希表专题"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 哈希表专题</h3></a></div><div class="item right"><a href="/KMP.html" rel="next" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/42bab566f107b9a16542343e0368fb77.jpg" title="KMP 算法"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Data Structure</span><h3>KMP 算法</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-151-%E9%A2%A0%E5%80%92%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E5%8D%95%E8%AF%8D"><span class="toc-number">1.</span> <span class="toc-text"> LeetCode 151. 颠倒字符串中的单词</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-number">1.1.</span> <span class="toc-text"> Method 1: 双指针</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%80%9D%E8%B7%AF"><span class="toc-number">1.2.</span> <span class="toc-text"> 算法思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%B5%81%E7%A8%8B"><span class="toc-number">1.3.</span> <span class="toc-text"> 算法流程</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.4.</span> <span class="toc-text"> 代码实现</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">1.5.</span> <span class="toc-text"> 复杂度分析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E4%B8%80%E6%AC%A1%E9%81%8D%E5%8E%86"><span class="toc-number">1.6.</span> <span class="toc-text"> Method 2: 一次遍历</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-208-%E5%AE%9E%E7%8E%B0-trie-%E5%89%8D%E7%BC%80%E6%A0%91"><span class="toc-number">2.</span> <span class="toc-text"> LeetCode 208. 实现 Trie (前缀树)</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF"><span class="toc-number">2.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E5%AD%97%E5%85%B8%E6%A0%91"><span class="toc-number">2.2.</span> <span class="toc-text"> Method: 字典树</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-28-%E5%AE%9E%E7%8E%B0-strstr"><span class="toc-number">3.</span> <span class="toc-text"> LeetCode 28. 实现 strStr ()</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-2"><span class="toc-number">3.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E6%9A%B4%E5%8A%9B%E6%90%9C%E7%B4%A2"><span class="toc-number">3.2.</span> <span class="toc-text"> Method 1: 暴力搜索</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-kmp-%E7%AE%97%E6%B3%95"><span class="toc-number">3.3.</span> <span class="toc-text"> Method 2: KMP 算法</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-344-%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-number">4.</span> <span class="toc-text"> LeetCode 344. 反转字符串</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-number">4.1.</span> <span class="toc-text"> Method: 双指针</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-459-%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-number">5.</span> <span class="toc-text"> LeetCode 459. 重复的子字符串</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-3"><span class="toc-number">5.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#methodkmp-%E7%AE%97%E6%B3%95"><span class="toc-number">5.2.</span> <span class="toc-text"> Method：KMP 算法</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-541-%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2-ii"><span class="toc-number">6.</span> <span class="toc-text"> LeetCode 541. 反转字符串 II</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-4"><span class="toc-number">6.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E5%8F%8C%E6%8C%87%E9%92%88-2"><span class="toc-number">6.2.</span> <span class="toc-text"> Method: 双指针</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-557-%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E5%8D%95%E8%AF%8D-iii"><span class="toc-number">7.</span> <span class="toc-text"> LeetCode 557. 反转字符串中的单词 III</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E5%8F%8C%E6%8C%87%E9%92%88%E5%8E%9F%E5%9C%B0%E8%A7%A3%E6%B3%95"><span class="toc-number">7.1.</span> <span class="toc-text"> Method 1: 双指针（原地解法）</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E5%8F%8C%E6%8C%87%E9%92%88%E4%BD%BF%E7%94%A8%E9%A2%9D%E5%A4%96%E7%A9%BA%E9%97%B4"><span class="toc-number">7.2.</span> <span class="toc-text"> Method 2: 双指针（使用额外空间）</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%89%91%E6%8C%87-offer-05-%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC"><span class="toc-number">8.</span> <span class="toc-text"> 剑指 Offer 05. 替换空格</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E9%81%8D%E5%8E%86%E6%B7%BB%E5%8A%A0"><span class="toc-number">8.1.</span> <span class="toc-text"> Method 1: 遍历添加</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E5%8E%9F%E5%9C%B0%E4%BF%AE%E6%94%B9%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-number">8.2.</span> <span class="toc-text"> Method 2: 原地修改（双指针）</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%89%91%E6%8C%87-offer-58-ii-%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-number">9.</span> <span class="toc-text"> 剑指 Offer 58-II. 左旋转字符串</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-5"><span class="toc-number">9.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E5%8F%8C%E6%8C%87%E9%92%88-3"><span class="toc-number">9.2.</span> <span class="toc-text"> Method: 双指针</span></a></li></ol></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/leetcode-binarysearch.html" rel="bookmark" title="LeetCode - 二分查找专题">LeetCode - 二分查找专题</a></li><li><a href="/leetcode-vectors.html" rel="bookmark" title="LeetCode - 数组专题">LeetCode - 数组专题</a></li><li><a href="/leetcode-list.html" rel="bookmark" title="LeetCode - 链表专题">LeetCode - 链表专题</a></li><li><a href="/leetcode-hashtable.html" rel="bookmark" title="LeetCode - 哈希表专题">LeetCode - 哈希表专题</a></li><li class="active"><a href="/leetcode-string.html" rel="bookmark" title="LeetCode - 字符串专题">LeetCode - 字符串专题</a></li><li><a href="/leetcode-stacks&queues.html" rel="bookmark" title="LeetCode - 栈与队列专题">LeetCode - 栈与队列专题</a></li><li><a href="/leetcode-binarytree.html" rel="bookmark" title="LeetCode - 二叉树专题">LeetCode - 二叉树专题</a></li><li><a href="/leetcode-traverse.html" rel="bookmark" title="LeetCode - 回溯专题">LeetCode - 回溯专题</a></li><li><a href="/leetcode-greedy.html" rel="bookmark" title="LeetCode - 贪心专题">LeetCode - 贪心专题</a></li><li><a href="/leetcode-dynamicprogramming.html" rel="bookmark" title="LeetCode - 动态规划专题">LeetCode - 动态规划专题</a></li><li><a href="/leetcode-doublepointer.html" rel="bookmark" title="LeetCode - 双指针专题">LeetCode - 双指针专题</a></li><li><a href="/leetcode-monotonicstacks.html" rel="bookmark" title="LeetCode - 单调栈专题">LeetCode - 单调栈专题</a></li><li><a href="/leetcode-search.html" rel="bookmark" title="LeetCode - 搜索专题">LeetCode - 搜索专题</a></li><li><a href="/leetcode-sort.html" rel="bookmark" title="LeetCode - 排序专题">LeetCode - 排序专题</a></li><li><a href="/leetcode-input&output.html" rel="bookmark" title="常见输入输出">常见输入输出</a></li><li><a href="/leetcode-analog.html" rel="bookmark" title="LeetCode - 模拟专题">LeetCode - 模拟专题</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/KMP.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/leetcode-hashtable.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-analog.html">LeetCode - 模拟专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/graphics-theory.html">图</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a></div><span><a href="/vscode-intro.html">vscode 使用</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-classes.html">C++ 类</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a><i class="ic i-angle-right"></i><a href="/categories/Tutorial/Hexo/" title="分类于Hexo">Hexo</a></div><span><a href="/hexo-build.html">hexo 博客搭建与配置</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/SQL/" title="分类于SQL">SQL</a></div><span><a href="/sql-basics.html">SQL 基础</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-binarytree.html">LeetCode - 二叉树专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a><i class="ic i-angle-right"></i><a href="/categories/Tutorial/LaTeX/" title="分类于LaTeX">LaTeX</a></div><span><a href="/latex-citation.html">LaTeX：跨 tex 文件的交叉引用</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-search.html">LeetCode - 搜索专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a></div><span><a href="/markdown.html">markdown</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/leetcode-string`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>