Leetcode 567.字符串的排列
2024-08-23 06:08:31
字符串的排列
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意:
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
思路
1.这道题,我们用到的算法是滑动窗口,思路大体是这样的:
首先字符串s1的排列的可能性应该是它的长度的阶乘,因为字符串长度可能为10000,所以找出所有排列情况是不太可能。我们可以转换思路,不要关注排列的形式,而是关注排列中元素的数量关系,比如aab,那么,转换为数量关系就是{a:2,b:1},因为S1长度为3,所以我们的窗口长度也为3,如果我们在S2的找到了这样一个窗口符合出现a的次数是两个,b是一个,那么S2就是包含S1的排列的。
2.什么是滑动窗口啊?
窗口表示的数组内我们重点关注的一块范围,比如此处的范围是e~i
滑动的意思及时,这个窗口会动,但是窗口的大小不变,比如此时右滑一位时,e就会离开,d就会加入。
3.再来理解一遍题?
我们说了,不要关注排列的形式,而是关注排列中元素的数量关系,比如aab,那么,转换为数量关系就是{a:2,b:1},因为S1长度为3,所以我们的窗口长度也为3,如果我们在S2的找到了这样一个窗口符合出现a的次数是两个,b是一个,那么S2就是包含S1的排列的。换到这个题中,同理:
所以,输出为True。
import java.util.Arrays; class Solution {
public boolean checkInclusion(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
int[] c1 = new int[26];
int[] c2 = new int[26];
for(char c : s1.toCharArray())
c1[c-'a']++; for(int i=0;i<l2;i++)
{
if(i>=l1)
--c2[s2.charAt(i-l1)-'a'];//先把坐标查过的
c2[s2.charAt(i)-'a']++;
if(Arrays.equals(c1, c2))
return true;
}
return false;
}
}
最新文章
- Java获取服务器网址
- 【JavaEE】SSH+Spring Security+Spring oauth2整合及example
- IOS之KVC和KVO(未完待续)
- Java中的String与常量池
- SGU 221.Big Bishops(DP)
- nettyclient异步获取数据
- AdaBoost对实际数据分类的Julia实现
- grep 同时满足多个关键字、满足任意关键字和排除关键字
- mssql sqlserver 禁止删除数据表中指定行数据(转自:http://www.maomao365.com/?p=5323)
- javaScript事件(八)事件类型之变动事件
- 错误:Bean property &#39;sessionFactory&#39; is not writable or has an invalid setter method.
- access数据库编号转换成统一3位数长度方法,不足3位前面补零
- SVN的安装
- Lua中and、or的一些特殊使用方法
- c# list修改某一个属性的值
- bug list
- TortoiseSVN 和 VisualSVN Server 使用教程
- Java并发--Timer和TimerTask
- SASS实现代码的重用:混合器Mixin、继承
- [Exception Spring 1] - Attribute value must not be null
热门文章
- ECLIPSE 取消自动更新
- bootstrap table保留多选框的分页
- UML复习1-2章
- CRM User Status profile中Business Transaction字段的用途
- [Rodbourn&#39;s Blog]How to export Excel plots to a vector image (EPS, EMF, SVG, etc.)
- 2017.12.25 Java中面向对象思想的深刻理解
- MySQL派生表(derived)优化一例
- HttpServletRequest HttpServletResponse ServletException 重新打开后报红解决方法
- 白鹭引擎eui控件的简单创建和管理方法
- python用requests请求,报SSL:CERTIFICATE_VERIFY_FAILED错误。