[LeetCode- Ch4. 투 포인터] 3. 문자열에서 모든 아나그램 찾기

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

Find All Anagrams in a String - LeetCode

 

1. rt만 이용해 추가할 경우 -> 타임리밋 발생

2. 초기값에서 문자를 하나씩 추가하는 방식으로 변경

 

1. rt만 이용해 반복해서 일치 확인

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int lt=0, rt=0, max=0, cnt=0;
        int n=p.length();
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> raw =new HashMap<>();
        for(char x: p.toCharArray()){
            raw.put(x, raw.getOrDefault(x,0)+1);
        }
        while(rt<s.length()-n+1){
            String tmp = s.substring(rt, rt+n);
            
            Map<Character, Integer> comp =new HashMap<>();
            
            for(char x: tmp.toCharArray()){
                comp.put(x, comp.getOrDefault(x,0)+1);
            }       
            if(comp.equals(raw)) result.add(rt);
            
            rt++;
        }
        return result;
    }
}

 

2. lt와 rt를 이용해 하나씩 추가삭제

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n=p.length();
        int lt=0, rt=n, max=0, cnt=0;
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> raw =new HashMap<>();
        Map<Character, Integer> comp =new HashMap<>();
        if(s.length()<p.length()) return  result;
        
        for(char x: p.toCharArray()){
            raw.put(x, raw.getOrDefault(x,0)+1);
        }
        String tmp="";
        for(int i=0;i<n;i++){
            tmp+=s.charAt(i);
        }
        for(char x: tmp.toCharArray()){
                comp.put(x, comp.getOrDefault(x,0)+1);
        }       
        if(comp.equals(raw)) result.add(lt);
        //System.out.println(tmp+" "+lt);
        lt++;
        
        //10-3
        //<=7
        while(rt<s.length()){
            comp.put(tmp.charAt(0), comp.get(tmp.charAt(0))-1);
            if(comp.get(tmp.charAt(0))==0) comp.remove(tmp.charAt(0));
            comp.put(s.charAt(rt), comp.getOrDefault(s.charAt(rt),0)+1);
                
            tmp=tmp.substring(1, tmp.length());
            tmp+=s.charAt(rt);
            //System.out.println(tmp+" "+lt);
            
            if(comp.equals(raw)) result.add(lt);
            
            lt++;
            rt++;
        }
        return result;
    }
}

---

+) 세련된 풀이

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
       	// 1
		List<Integer> result = new ArrayList<>();
		if (s == null || s.length() == 0 || p == null || p.length() == 0 || s.length() < p.length())
			return result;
		// 2
		int[] pArr = new int[26];//
		for (int i = 0; i < p.length(); i++) {
			pArr[p.charAt(i) - 'a']++;// [1,1,1,1,0,0,0.......]
		}

		for (int i = 0; i < s.length() - p.length() + 1; i++) {
			int[] sArr = new int[26];
			for (int j = 0; j < p.length(); j++) {
				System.out.print(s.charAt(i + j));
				System.out.println("i " + i + " j " + j);
				sArr[s.charAt(i + j) - 'a']++; // 0+, 1+

			}
			System.out.println();
			if (check(pArr, sArr)) {
				result.add(i);
			}
		}
		return result;
	}

	private boolean check(int[] pArr, int[] sArr) {
		for (int i = 0; i < pArr.length; i++) {
			if (pArr[i] != sArr[i]) {
				return false;
			}
		}
		return true;
	}

	public List<Integer> solve(String s, String t) {
		List<Integer> result = new LinkedList<>();
		if (t.length() > s.length())
			return result;
		Map<Character, Integer> map = new HashMap<>();
		for (char c : t.toCharArray()) {
			map.put(c, map.getOrDefault(c, 0) + 1);
		}

		int counter = map.size();
		int left = 0, right = 0;

		while (right < s.length()) {
			char c = s.charAt(right);
//			System.out.println("c: " + c);
			if (map.containsKey(c)) {
				map.put(c, map.get(c) - 1);
				if (map.get(c) == 0)
					counter--;
			}
			right++;

			while (counter == 0) {
				char c2 = s.charAt(left);
				if (map.containsKey(c2)) {
					map.put(c2, map.get(c2) + 1);
					if (map.get(c2) > 0) {
						counter++;
						System.out.println("cou " + counter);
					}
				}
				if (right - left == t.length()) {
					result.add(left);
				}

				left++;

			}

		}
		return result;
	}
}

 

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> answer = new ArrayList<>();
        int n=s.length();
        int m=p.length();
        if(n<m) return answer;
        
        Map<Character, Integer> pmap = new HashMap<>();
        
        for(char c: p.toCharArray()){
            pmap.put(c, pmap.getOrDefault(c, 0)+1);
        }
        Map<Character, Integer> comp = new HashMap<>();
        for(int i=0;i<m;i++){
            char c=s.charAt(i);
            comp.put(c, comp.getOrDefault(c, 0)+1);
        }
        if(comp.equals(pmap)) answer.add(0);
        
        //7까지, 10-3
        for(int i=1; i<n-m+1;i++){
            char c=s.charAt(i-1);
            comp.put(c, comp.getOrDefault(c, 0)-1);
            if(comp.get(c)==0) comp.remove(c);
            
            char nc=s.charAt(i+m-1);
            comp.put(nc, comp.getOrDefault(nc, 0)+1);
            if(comp.equals(pmap)) answer.add(i);
        }
        return answer;
    }
}