[LeetCode] 567. Permutation in String

geekzhou 發布于2019-08-16 13:32 / 3118人閱讀

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

云服務器 GPU云服務器 LeetCode_String Permutation 最新域名 av567.net LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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