[LintCode] Permutation in String

wenshi11019 發布于2019-08-15 18:16 / 1187人閱讀

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

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

Solution

public class Solution {
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: if s2 contains the permutation of s1
     */
    public boolean checkInclusion(String s1, String s2) {
        int len = s1.length();
        for (int i = 0; i <= s2.length()-len; i++) {
            if (isPermutation(s2.substring(i, i+len), s1)) return true;
        }
        return false;
    }
    
    //use the method of #String Permutation
    public boolean isPermutation(String s1, String s2) {
        if (s1 == null) return s2 == null;
        if (s2 == null) return s1 == null;
        if (s1.length() != s2.length()) return false;
        
        int[] dict = new int[256];
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        for (char ch: c1) {
            dict[(int)ch]++;
        }
        for (char ch: c2) {
            dict[(int)ch]--;
            if (dict[(int)ch] < 0) return false;
        }

        return true;
    }
}

云服務器 GPU云服務器 Permutation LintCode LintCode134_LRU String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69721.html

[LintCode] Next Permutation II [Next Permutation]

摘要：從末位向前遍歷，假設循環開始全是倒序排列，如當第一次出現正序的時候，如的和此時從數列末尾向前循環到，找到第一個比大的交換這兩個數，變成倒置第位到末位的數為正序排列這里的是完全倒置的排列，如，即上面循環的情況完全沒有出現， Problem Implement next permutation, which rearranges numbers into the lexicographic...

mikasa 2019-08-14 15:15 評論0 收藏0
[LintCode] Permutation Index I & Permutation I

摘要：我覺得雖然在里分類是，但其實是一道難題。思路如下搞一個哈希表，存儲數組中每一位的后面小于它的數的個數。與上一題的不同之處時會有重復的數。當然，每個重復數的都要階乘，例如有個，個，就是。是所有排列的次數和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 評論0 收藏0
[LintCode] Previous Permutation

Problem Given a list of integers, which denote a permutation. Find the previous permutation in ascending order. Notice The list may contains duplicate integers. Example For [1,3,2,3], the previous per...

Pines_Cheng 2019-08-14 15:44 評論0 收藏0
[LintCode] Permutation Sequence

摘要：做法先把這個數放入一個數組里，同時計算出的階乘。假設這一組是第組，第一個數就是，同時刪去這個數，并讓除以取余作為新的。如此循環，這樣，下一組的成員數減少了，要找的位置也更為精確了。 Problem Given n and k, return the k-th permutation sequence. Example For n = 3, all permutations are li...

Jacendfeng 2019-08-14 15:19 評論0 收藏0
[LeetCode] 567. Permutation in String

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 strings permutations is the substring of the second string.E...

geekzhou 2019-08-16 13:32 評論0 收藏0