[LeetCode/Medium] 438. Find All Anagrams in a String

1. Input

1) String s

2) String p

 

2. Output

1) s의 부분 문자열 중 p의 애너그램의 시작 인덱스를 담은 List<Integer>

// 애너그램이란 문자를 재배열했을 때 다른 단어와 같게 되는 단어를 말한다.

 

3. Constraint

1) 1 <= s.length, p.length <= 3 * 10^4

2) s와 p는 영어 소문자로만 이루어져 있다.

 

4. Example

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

설명:

- s.substring(0,3) == "cba"는 p의 애너그램이다.

- s.substring(6,9) == "bac“는 p의 애너그램이다.

 

5. Code

1) 첫 코드(2023/02/21)

List<Integer> answer = new ArrayList<Integer>();
char[] c = p.toCharArray();
Arrays.sort(c);
p = new String(c);
for(int i=0 ; i<=s.length()-p.length() ; i++){
    c = s.substring(i,i+p.length()).toCharArray();
    Arrays.sort(c);
    if(p.equals(new String(c))) answer.add(i);
}
return answer;

- 시간은 무지 오래 걸렸는데, 메모리 사용량은 준수한 편이었다. 직관적으로 푼거라 효율성이 많이 떨어진다.