Problem
题目大意：给你s1, s2，问你s2的子串中是否存在s1的一个排列。
https://leetcode.com/problems/permutation-in-string/description/
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: Sliding Window
Time Complexity: O(l1 + l2 * 26) = O(l1 + l2)
Space Complexity: O(26 * 2) = O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 12 ms class Solution { public: bool checkInclusion(string s1, string s2) { int l1 = s1.length(); int l2 = s2.length(); vector<int> c1(26); vector<int> c2(26); for (const char c : s1) ++c1[c - 'a']; for (int i = 0; i < l2; ++i) { if (i >= l1) --c2[s2[i - l1] - 'a']; ++c2[s2[i] - 'a']; if (c1 == c2) return true; } return false; } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment