又到了面试季,最近问了一个问题,好像不太好答,于是自己试试
leetcode 567 https://leetcode.com/problems/…
package test20190925.test20190925; import java.util.Arrays; public class SubStringCheck { public static String sortStringChar(String s) { char[] chars = s.toCharArray(); Arrays.sort(chars); return new String(chars); } public static boolean checkContains(String s1, String s2) { String s1Sorted = sortStringChar(s1); //System.out.println(s1Sorted); int s1Length = s1Sorted.length(); int s2Length = s2.length(); for (int i = 0; i <= s2Length - s1Length; i++) { String s2Capture = s2.substring(i, i + s1Length); //System.out.println(s2Capture); String s2CaptureSorted = sortStringChar(s2Capture); if (s1Sorted.equals(s2CaptureSorted)) { return true; } } return false; } public static void main(String[] args) { System.out.println(checkContains("abc", "eidboaoo")); } }
2021-9-30 又搞了一个 c++ 的,这个快很多,内存也小
class Solution { public: bool checkInclusion(string s1, string s2) { vector<int> s1count(26), s2count(26); for (size_t i = 0; i < s1.length() && i < s2.length(); i++) { s1count[s1.at(i) - 'a']++; s2count[s2.at(i) - 'a']++; } for (size_t i = s1.length() - 1; i < s2.length(); i++) { if (s1count == s2count) { return true; } if (i + 1 < s2.length()) { s2count[s2.at(i - s1.length() + 1) - 'a']--; s2count[s2.at(i + 1) - 'a']++; } } return false; } };
2024-1-18 补充了一个 Java 版本的数组实现
package com.test20231227; import java.util.Arrays; import java.util.Date; public class SubStringCheck { public static boolean checkInclusion(String s1, String s2) { int[] s1count = new int[26]; int[] s2count = new int[26]; final int ascii_char_a = (int)'a'; for (int i = 0; i < s1.length() && i < s2.length(); i++) { s1count[(int)s1.charAt(i) - ascii_char_a]++; s2count[(int)s2.charAt(i) - ascii_char_a]++; } for (int i = s1.length() - 1; i < s2.length(); i++) { if (Arrays.equals(s1count, s2count)) { return true; } if (i + 1 < s2.length()) { s2count[(int)s2.charAt(i - s1.length() + 1) - ascii_char_a]--; s2count[(int)s2.charAt(i + 1) - ascii_char_a]++; } } return false; } public static void main(String[] args) { System.out.println(checkInclusion("abcd", "eidcboaoo")); } }