Snap面经题目:find anagram

0002505492

题目:
给一长一短两个 string,返回长 string (N) 里面有没有 substring 是短 string (M) 的 anagram,最好给出O(N)的解法。
思路:
与leetcode 76 相似。
代码:


public class Solution {
	public static boolean find(String s, String t)
	{
		int[] map = new int[128];
		for(char c: t.toCharArray()) map++;
		int count = t.length(), start = 0, end = 0;
		char[] array = s.toCharArray();
		while(end < s.length())
		{
			if(map[array[end++]]-- > 0) count--;
			while(count == 0)
			{
				if(end - start == t.length())
				{
					System.out.println(s.substring(start, end));
					return true;
				}
				if(map[array[start++]]++ >= 0) count++;
			}
		}
		return false;
	}
	public static void main(String[] args)
	{
		String S = "ABCHSEDABC";
		String T = "ABCDE";
		System.out.println(find(S,T));
	}
}

output:

EDABC
true

1846total visits,2visits today