LeetCode438 Find All Anagrams in a String

2023-12-23 23:18

本文主要是介绍LeetCode438 Find All Anagrams in a String,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目要求:

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"Output:
[0, 6]Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"Output:
[0, 1, 2]Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

题目虽然是EASY但是一点也不简单,使用划窗法进行处理

这个代码时间超时

public class Solution {public List<Integer> findAnagrams(String s, String p) {//使用暴力搜索的方法进行处理//这种方法计算时间超时List<Character> set = new LinkedList<>();List<Character> setTem = new LinkedList<>();List<Integer> list = new ArrayList<>();char[] arr = p.toCharArray();for(char c : arr) set.add(c);int num = arr.length;for(int i = 0; i < s.length() - num + 1; i++) {setTem.clear();setTem.addAll(set);for(int j = 0; j < num; j++) {if(setTem.contains(s.charAt(i + j))) setTem.remove((Character) s.charAt(i + j));else break;if(setTem.size() == 0) list.add(i);}}return list;}
}

滑窗法可以

public class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> list = new ArrayList<>();if(s.length() == 0 || p.length() == 0 || p.length() > s.length()) return list;int[] hasharr = new int[256];char[] arrp = p.toCharArray();for (char c : arrp) hasharr[c]++;int right = 0, left = 0;int count = p.length();while(right < s.length()) {if(hasharr[s.charAt(right++)]-- >= 1) count--;if(count == 0) list.add(left);if(right - left == p.length() && hasharr[s.charAt(left++)]++ >= 0) count++;}return list;}
}



这篇关于LeetCode438 Find All Anagrams in a String的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/529800

相关文章

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

MongoDB学习—(6)MongoDB的find查询比较符

首先,先通过以下函数向BookList集合中插入10000条数据 function insertN(obj,n){var i=0;while(i<n){obj.insert({id:i,name:"bookNumber"+i,publishTime:i+2000})i++;}}var BookList=db.getCollection("BookList")调用函数,这样,BookList

hdu2072(string的应用)

单词数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25447    Accepted Submission(s): 5957 Problem Description lily的好朋友xiaoou333最近很空,他

【UVA】10739 - String to Palindrome(动态规划)

比较水的动态规划 dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数 其中删除操作和添加操作本质上是一样的。 三个状态转移方程: dp[i][j] = min(dp[i][j] ,dp[i + 1][j]); dp[i][j] = min(dp[i][j] ,dp[i + 1][j - 1]); dp[i][j] = min(dp[i][j] ,dp[

理解String的compareTo()方法返回值

compareTo()的返回值是整型,它是先比较对应字符的大小(ASCII码顺序), 如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值。 如果第一个字符和参数的第一个字符相等,则以第二个字符和参数的第二个字符作比较, 以此类推,直至比较的字符或被比较的字符有一方全比较完,这时就比较字符的长度。 我们可以通过阅读源码加深对compareTo()的理解: comp

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

【NodeJS】Error: Cannot find module 'ms'

转载自:http://blog.csdn.net/echo_ae/article/details/75097004 问题: Error: Cannot find module 'ms'at Function.Module._resolveFilename (module.js:469:15)at Function.Module._load (module.js:417:25)at Module

leetCode#448. Find All Numbers Disappeared in an Array

Description Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this

leetcode#541. Reverse String II

题目 Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of

访问controller404:The origin server did not find a current representation for the target resource

ider build->rebuild project。Rebuild:对选定的目标(Project),进行强制性编译,不管目标是否是被修改过。由于 Rebuild 的目标只有 Project,所以 Rebuild 每次花的时间会比较长。 参考:资料