資訊專欄INFORMATION COLUMN
Problem
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string"s permutations is the substring of the second string.
Example 1:
Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1= "ab" s2 = "eidboaoo" Output: False
Note:
The input strings only contain lower case letters. The length of both given strings is in range [1, 10,000].Solution
class Solution {
public boolean checkInclusion(String s1, String s2) {
int l1 = s1.length(), l2 = s2.length();
if (l2 < l1) return false;
Map map = new HashMap<>();
for (int i = 0; i < l1; i++) {
map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0)+1);
map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0)-1);
}
if (checkMap(map)) return true;
for (int i = l1; i < l2; i++) {
map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0)-1);
map.put(s2.charAt(i-l1), map.get(s2.charAt(i-l1))+1);
if (checkMap(map)) return true;
}
return false;
}
private boolean checkMap(Map map) {
for (Map.Entry entry: map.entrySet()) {
if (entry.getValue() != 0) return false;
}
return true;
}
}
using int array as map
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() > s2.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s1.length(); i++) {
count[s1.charAt(i)-"a"]++;
count[s2.charAt(i)-"a"]--;
}
if (allZero(count)) return true;
for (int i = s1.length(); i < s2.length(); i++) {
count[s2.charAt(i)-"a"]--;
count[s2.charAt(i-s1.length())-"a"]++;
if (allZero(count)) return true;
}
return false;
}
private boolean allZero(int[] arr) {
for (int i: arr) {
if (i != 0) return false;
}
return true;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71904.html
摘要：找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成，則第個(gè)全排列的第一位是。然后將得到，這個(gè)就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...
摘要：題目要求假設(shè)按照題中給的排列組合的順序，假設(shè)有個(gè)數(shù)字，返回第個(gè)排列組合的結(jié)果。最后在個(gè)位上，選擇中的第一個(gè)。這時(shí)知道以第位為開頭的結(jié)果值有此時(shí)第個(gè)結(jié)果集在該位上的選擇為。依次往后類推，直至到最后一位。 題目要求 The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling...
摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結(jié)果中是否有回文。而中心對(duì)稱點(diǎn)如果是字符，該字符會(huì)是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...
摘要：因?yàn)樵黾痈呶粫?huì)帶來更大的增益。所以對(duì)于一個(gè)長(zhǎng)為的序列，我們?cè)黾拥谖坏那疤崾?，前位已?jīng)達(dá)到了最大排列方法。因?yàn)槭钦蚁乱粋€(gè)數(shù)，所以我們要找一個(gè)比小卻盡可能大的數(shù)，所以找到。把換到的位置后，后三位仍然是個(gè)降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...
Problem Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. Example Given s = aabb, return [abba,baa...
閱讀 1140·2021-09-22 15:32
閱讀 1735·2019-08-30 15:53
閱讀 3267·2019-08-30 15:53
閱讀 1420·2019-08-30 15:43
閱讀 465·2019-08-28 18:28
閱讀 2584·2019-08-26 18:18
閱讀 677·2019-08-26 13:58
閱讀 2539·2019-08-26 12:10
