Java using isAnagram() helper function, easy to understand


  • 13
    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if (p == null || s == null || s.length() < p.length()) return res;
            int m = s.length(), n = p.length();
            for (int i = 0; i < m-n+1; i++) {
                String cur = s.substring(i, i+n);
                if (helper(cur, p)) res.add(i);
            }
            return res;
        }
        public boolean helper(String a, String b) {
            if (a == null || b == null || a.length() != b.length()) return false;
            int[] dict = new int[26];
            for (int i = 0; i < a.length(); i++) {
                char ch = a.charAt(i);
                dict[ch-'a']++;
            }
            for (int i = 0; i < b.length(); i++) {
                char ch = b.charAt(i);
                dict[ch-'a']--;
                if (dict[ch-'a'] < 0) return false;
            }
            return true;
        }
    }
    

  • 0
    N

    Its efficiency is too bad.


  • 0
    W

    That was my first solution. It is not the most efficient one and it got barely accepted. But I worked that out myself. So you got an up vote from me.


  • 0

    Also my first solution. Never heard of sliding window before this problem.


  • 0
    S

    @vegito2002 "Sliding window" seems like Tcp/ip protocol...


  • 0

    @shao892607124 In a way I guess. The algorithm itself is quite brilliant though :)


  • 0

    @vegito2002 It more likely an algorithm that calculate the distance between two strings using sliding window, and the sliding window of the most concise one, its window width is growth from 1 to n.


  • 0
    J

    I use the same idea, but it cause time exceed error. Could someone can help me what is the problem of my code?

    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List list = new LinkedList();
            p = sortString(p);
            if(s == null || s.length() == 0) return list;
            for(int i=0; i<s.length()-p.length()+1; i++){
                String sub = s.substring(i,i+p.length());
                if(sortString(sub).equals(p)) list.add(i);
            }
            return list;
        }
        
        private String sortString(String s){
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            return String.valueOf(ch);
        }
    }
    

  • 0

    @JA sort will be nlogn, so the algorithm will be $n^2log(n)$,


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.