[剑指offer专项突击版-Java解法]剑指 Offer II 014. 字符串中的变位词
2021/9/24 22:12:29
本文主要是介绍[剑指offer专项突击版-Java解法]剑指 Offer II 014. 字符串中的变位词,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer II 014. 字符串中的变位词
题目描述
给定两个字符串 s1
和 s2
,写一个函数来判断 s2
是否包含 s1
的某个变位词。
换句话说,第一个字符串的排列之一是第二个字符串的 子串 。
示例 1:
输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").
示例 2:
输入: s1= "ab" s2 = "eidboaoo" 输出: False
提示:
1 <= s1.length, s2.length <= 104
s1
和s2
仅包含小写字母
思路解析
1.用两个hash表来存储两个字符串的字母的个数
2.看清楚题意,就是s2一个子区间内的所有字符数和s1的相同就行,我们一下就能想到滑动窗口了
3.用一个set去存储s1字符串其中的字母,能够给加速查找,就没必要26个字母都遍历一次了
4.简单的滑动窗口的实现
代码实现
class Solution { public boolean checkInclusion(String s1, String s2) { int[] hash1 = new int[26]; int[] hash2 = new int[26]; char[] chars1 = s1.toCharArray(); char[] chars2 = s2.toCharArray(); Set<Character> set = new HashSet<>(); for(int i = 0;i<chars1.length;i++) { if(!set.contains(chars1[i])) set.add(chars1[i]); hash1[chars1[i]-'a']++; } int left=0,right = 0; while(right<chars2.length) { hash2[chars2[right]-'a']++; right++; if(right-left>=chars1.length) { if(isSub(set,hash1,hash2)) return true; else { hash2[chars2[left]-'a']--; left++; } } } return false; } public boolean isSub(Set<Character> set,int[] hash1,int[] hash2) { for(char c :set) { if(hash1[c-'a']!=hash2[c-'a']) return false; } return true; } }
欢迎大佬们关注小弟的博客https://blog.csdn.net/qq_41522089
这篇关于[剑指offer专项突击版-Java解法]剑指 Offer II 014. 字符串中的变位词的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-19Token处理入门教程:新手必看指南
- 2024-09-19如何应对被动登出课程的情况:新手必读指南
- 2024-09-19打包优化课程:初学者的必备指南
- 2024-09-19登录鉴权课程:新手入门教程
- 2024-09-19动态菜单项课程:新手入门详解
- 2024-09-19动态路由表课程:新手入门教程
- 2024-09-19动态面包屑课程:入门与实践指南
- 2024-09-19动态权限课程:新手入门教程
- 2024-09-19动态主题处理课程:新手入门教程
- 2024-09-19服务器购买课程:新手入门必学指南