资讯专栏INFORMATION COLUMN

[LintCode] Permutation in String

wenshi11019 / 1160人阅读

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

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

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

相关文章

  • [LintCode] Next Permutation II [Next Permutation]

    摘要:从末位向前遍历,假设循环开始全是倒序排列,如当第一次出现正序的时候,如的和此时从数列末尾向前循环到,找到第一个比大的交换这两个数,变成倒置第位到末位的数为正序排列这里的是完全倒置的排列,如,即上面循环的情况完全没有出现, Problem Implement next permutation, which rearranges numbers into the lexicographic...

    mikasa 评论0 收藏0
  • [LintCode] Permutation Index I & Permutation I

    摘要:我觉得虽然在里分类是,但其实是一道难题。思路如下搞一个哈希表,存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然,每个重复数的都要阶乘,例如有个,个,就是。是所有排列的次数和,返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

    lucas 评论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 评论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 评论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 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<