[LeetCode] 567. Permutation in String

geekzhou 发布于2019-08-16 13:32 / 3000人阅读

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;
    }
}

云服务器混合云 LeetCode_String Permutation 最新域名 av567.net LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71904.html

[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0
leetcode60. Permutation Sequence

摘要：题目要求假设按照题中给的排列组合的顺序，假设有个数字，返回第个排列组合的结果。最后在个位上，选择中的第一个。这时知道以第位为开头的结果值有此时第个结果集在该位上的选择为。依次往后类推，直至到最后一位。题目要求 The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling...

xiaokai 2019-08-15 10:38 评论0 收藏0
[Leetcode] Palindrome Permutation 回文变换

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判断回文的方法来判断结果中是否有回文。而中心对称点如果是字符，该字符会是奇数次，如果在两个字符之间，则所有字符都是出现偶数次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 评论0 收藏0
[Leetcode] Next Permutation 下一个排列

摘要：因为增加高位会带来更大的增益。所以对于一个长为的序列，我们增加第位的前提是，前位已经达到了最大排列方法。因为是找下一个数，所以我们要找一个比小却尽可能大的数，所以找到。把换到的位置后，后三位仍然是个降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...

young.li 2019-08-14 12:34 评论0 收藏0
[LeetCode] 267. Palindrome Permutation II

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...

huashiou 2019-08-16 12:40 评论0 收藏0