BruteForceSearch HackerRank Algorithms in Java ‘Sherlock and Anagrams’ solution

Problem

Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string. Given a string, find the number of pairs of substrings of the string that are anagrams of each other. For example s = mom, the list of all anagrammatic pairs is [m,m],[mo,om] at positions [[0],[2]], [[0,1],[1,2]] respectively.

• Constraints
  2 <= |s| <= 100

Sample Input 1

2
ifailuhkqq
kkkk

Sample Output 1

3
10

Solution

anagrams가 뭔지 이해하는 데 시간을 거의 다 썼다. 처음에는 데칼코마니 같은 것인가 생각했는데, 첫번째 문자열에서 사용했던 모든 문자가 그대로 두번째 문자열에서도 사용되는 것을 말하는 것 같다. (순서와 상관 없이!) 그래서 예제를 보면 “ifailuhkqq” 여기서 답은 [i,i], [ifa, fai], [q,q] 세가지이다. 다만, ifa, fai를 보면 알 수 있듯이 부분 문자열의 순서는 반드시 유지된다.

• 제한 사항에 문자열은 100을 넘기지 않기 때문에 완전탐색을 이용했다.
• 문자열의 substring을 하나하나 다 구해서 리스트에 저장한다.
• 리스트에서 하나하나 다 꺼내서 비교한다. 이미 확인한 문자를 건너뛰기 위해 visit[] 배열을 사용했다.
• anagrams는 반드시 서로 문자의 개수가 동일하므로 일찌감치 처리해준다. if(s1.length() != s2.length()) return false;
• 그것들의 개수 ans 변수의 값을 증가시키고 이것을 반환한다.

Code

  static boolean isAnagrams(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        
        int cnt = 0;
        boolean[] visit = new boolean[s2.length()];
        for(int i = 0; i < s1.length(); i++) {
            for(int j = 0; j < s2.length(); j++) {
                if(s1.charAt(i) == s2.charAt(j) && !visit[j]) {
                    cnt++; visit[j] = true; break;
                }
            }
        }
        return cnt == s2.length()? true : false;
    }
    // Complete the sherlockAndAnagrams function below.
    static int sherlockAndAnagrams(String s) {
        List<String> list = new ArrayList<>();
        for(int i = 0; i < s.length(); i++) {
            for(int j = i + 1; j <= s.length(); j++) 
                list.add(s.substring(i, j));
        }
        
        int ans = 0;
        for(int i = 0; i < list.size(); i++) {
            for(int j = i + 1; j < list.size(); j++) {
                if(isAnagrams(list.get(i), list.get(j))) ans++;
            }
        }
        return ans;
    }