题目描述
字符串的排列
难度:中等
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,s1 的排列之一是 s2 的 子串。
示例 1:
输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).
示例 2:
输入:s1= “ab” s2 = “eidboaoo”
输出:false
提示:
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
解题思路
题目大意: 就是看字符串s2是否包含s1的排列,所白了就是只要是连续包含s1的字符就行,不考虑顺序。
解题思路:
滑动窗口思想,来个need数组,来存所需的字符,同时定义l和r两个指针,不断右移右指针,同时更新need数组,如果符合情况就返回true,不符合继续移动窗口,最后还找不到符合的就返回false。
代码
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
|
class Solution { public boolean checkInclusion(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); if (l1 > l2 || "" .equals(s1) || "" .equals(s2)) { return false ; } //创建个need数组,表示所需要的字符以及个数,通过遍历s1的得到 int [] need = new int [ 26 ]; for ( int i = 0 ; i < l1; i++) { need[s1.charAt(i) - 'a' ]++; } //滑动窗口 int l = 0 , r = 0 ; //如果l=l2-l1就可以停了,后面的长度都不够了 while (l <= l2 - l1) { //如果符合条件,即need[s2.charAt(r) - 'a'] > 0,就是当前窗口右端碰到的的是需要的字符 while (r < l + l1 && need[s2.charAt(r) - 'a' ] > 0 ) { //更新所需的字符个数 need[s2.charAt(r) - 'a' ]--; //扩大窗口范围 r++; } //找到所符合的个数了,就是需要的子串已经找到了 if (r == l + l1) { return true ; } //移动左窗口,这样左边的字符从窗口中退出来了,就需要把need[s2.charAt(l) - 'a']++,维护need need[s2.charAt(l) - 'a' ]++; //移动左边的指针 l++; } return false ; } } |
完整代码【含测试代码和三种解决方案】
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
|
package com.keafmd.Likou.Day0729; import java.util.Arrays; import java.util.HashMap; /** * Keafmd * * @ClassName: StringArrangement * @Description: https://leetcode-cn.com/problems/permutation-in-string/ * @author: 牛哄哄的柯南 * @date: 2021-07-29 9:11 */ public class StringArrangement { public static void main(String[] args) { String s1 = "hello" , s2 = "ooolleooolleh" ; boolean b = new StringArrangementSolution().checkInclusion(s1, s2); System.out.println(b); } } class StringArrangementSolution { public boolean checkInclusion(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); if (l1 > l2 || "" .equals(s1) || "" .equals(s2)) { return false ; } //创建个need数组,表示所需要的字符以及个数,通过遍历s1的得到 int [] need = new int [ 26 ]; for ( int i = 0 ; i < l1; i++) { need[s1.charAt(i) - 'a' ]++; } //滑动窗口 int l = 0 , r = 0 ; //如果l=l2-l1就可以停了,后面的长度都不够了 while (l <= l2 - l1) { //如果符合条件,即need[s2.charAt(r) - 'a'] > 0,就是当前窗口右端碰到的的是需要的字符 while (r < l + l1 && need[s2.charAt(r) - 'a' ] > 0 ) { //更新所需的字符个数 need[s2.charAt(r) - 'a' ]--; //扩大窗口范围 r++; } //找到所符合的个数了,就是需要的子串已经找到了 if (r == l + l1) { return true ; } //移动左窗口,这样左边的字符从窗口中退出来了,就需要把need[s2.charAt(l) - 'a']++,维护need need[s2.charAt(l) - 'a' ]++; //移动左边的指针 l++; } return false ; } } class StringArrangementSolution2 { public boolean checkInclusion(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); if (s1 == null || s2 == null || l1 > l2 || s1 == "" || s2 == "" ) { return false ; } int [] need = new int [ 26 ]; for ( int i = 0 ; i < l1; i++) { need[s1.charAt(i) - 'a' ]--; } int l = 0 , r = 0 ; int count = 0 ; while (r < l2) { int x = s2.charAt(r) - 'a' ; need[x]++; while (need[x] > 0 ) { need[s2.charAt(l) - 'a' ]--; l++; } if (r - l + 1 == l1) { return true ; } r++; } return false ; } } class StringArrangementSolution1 { public boolean checkInclusion(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); if (s1 == null || s2 == null || l1 > l2 || s1 == "" || s2 == "" ) { return false ; } int [] num1 = new int [ 26 ]; int [] num2 = new int [ 26 ]; for ( int i = 0 ; i < s1.length(); i++) { num1[s1.charAt(i) - 'a' ]++; num2[s2.charAt(i) - 'a' ]++; } if (Arrays.equals(num1, num2)) { return true ; } int l = 0 , r = 0 ; int count = 0 ; for ( int i = l1; i < l2; i++) { num2[s2.charAt(i) - 'a' ]++; num2[s2.charAt(i - l1) - 'a' ]--; if (Arrays.equals(num1, num2)) { return true ; } } return false ; } } |
总结
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!
原文链接:https://blog.csdn.net/weixin_43883917/article/details/119219733