写点什么

【LeetCode】字符串的排列题解

用户头像
HQ数字卡
关注
发布于: 2021 年 02 月 10 日

题目

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。


换句话说,第一个字符串的排列之一是第二个字符串的子串。

代码

public class DayCode {    public static void main(String[] args) {        String s1 = "ab", s2 = "eidbaooo";        boolean ans = new DayCode().checkInclusion(s1, s2);        System.out.println("ans is " + ans);    }
/** * https://leetcode-cn.com/problems/permutation-in-string/ * @param s1 * @param s2 * @return */ public boolean checkInclusion(String s1, String s2) { int n = s1.length(); int m = s2.length(); if (n > m) { return false; } int[] cnt1 = new int[26]; int[] cnt2 = new int[26]; for (int i = 0; i < n; ++i) { ++cnt1[s1.charAt(i) - 'a']; ++cnt2[s2.charAt(i) - 'a']; } if (Arrays.equals(cnt1, cnt2)) { return true; } for (int i = n; i < m; ++i) { ++cnt2[s2.charAt(i) - 'a']; --cnt2[s2.charAt(i - n) - 'a']; if (Arrays.equals(cnt1, cnt2)) { return true; } } return false; }}
复制代码

总结

  • 上述代码的时间复杂度 O(n * n), 空间复杂度是 O(1)

  • 上述方法不是最优解,只是滑动窗口的基本使用,还有很大的优化空间。


发布于: 2021 年 02 月 10 日阅读数: 11
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】字符串的排列题解