[알고리즘] Find All Anagrams in a String (java 풀이) leetcode

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Find All Anagrams in a String - LeetCode

 

 

문제

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

 

예제

Input: s: "cbaebabacd" p: "abc" Output: [0, 6]

 

Input: s: "abab" p: "ab" Output: [0, 1, 2]

 

Input: s: "bacdgabcda" p: "abcd" Output: [0, 5, 6]

 

 

풀이

- int형배열을 256크기로 생성하여   s와 p 의 아스키코드를 이용한다.

import java.util.ArrayList;
import java.util.List;

public class FindAllAnagram {
	public static void main(String[] args) {
		String txt = "BACDGABCDA";
		String pat = "ABCD";

		ArrayList<Integer> list = new ArrayList<>();
		list = (ArrayList<Integer>) solve(txt, pat);

		System.out.println(list.toString());
	}

	public static List<Integer> solve(String txt, String pat) {

		ArrayList<Integer> list = new ArrayList<>();
		int[] patArr = new int[256];
		for (int i = 0; i < pat.length(); i++) {
			patArr[pat.charAt(i)]++;
		}

		for (int i = 0; i < txt.length() - pat.length() + 1; i++) {
			int[] txtArr = new int[256];
			for (int j = 0; j < pat.length(); j++) {
				txtArr[txt.charAt(i + j)]++;
			}

			if (check(patArr, txtArr)) {
				list.add(i);
			}

		}
		return list;

	}

	public static boolean check(int[] patArr, int[] txtArr) {
		for (int i = 0; i < patArr.length; i++) {
			if (patArr[i] != txtArr[i]) {
				return false;
			}
		}

		return true;
	}

}