50 DSA questions: #18, #19, #20

#18. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

public class Exercise18 {
    private static final String FIRST = "rat"; //"anagram";
    private static final String SECOND = "car"; // "nagaram";

    private void solve() {
        Map<Byte, Integer> occurrenceMap = new HashMap<>();
        for (byte key : FIRST.getBytes()) {
            occurrenceMap.put(key, occurrenceMap.containsKey(key) ? occurrenceMap.get(key) + 1 : 1);
        }
        for (byte key : SECOND.getBytes()) {
            if (!occurrenceMap.containsKey(key)) {
                System.out.println("False");
                return;
            }

            int n = occurrenceMap.get(key) - 1;
            if (n == 0) {
                occurrenceMap.remove(key);
            } else {
                occurrenceMap.put(key, n);
            }
        }

        System.out.println("True");
    }

    public static void main(String args[]) {
        new Exercise18().solve();
    }
}

#19. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

public class Exercise19 {
    private static final String[] STRS = {"eat","tea","tan","ate","nat","bat"};

    private String getSortedWord(String word) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    private void solve() {
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String str : STRS) {
            final String key = getSortedWord(str);
            if (!anagramMap.containsKey(key)) {
                anagramMap.put(key, new ArrayList<>());
            }
            anagramMap.get(key).add(str);
        }
        System.out.println(anagramMap.values());
    }

    public static void main(String args[]) {
        new Exercise19().solve();
    }
}

#20. Valid Parentheses

Given a string s containing just the characters '(' , ')' , '{' , '}' , '[' and ']' , determine if the input string is valid. An input string is valid if:

• Open brackets must be closed by the same type of brackets. 
• Open brackets must be closed in the correct order. 
• Every close bracket has a corresponding open bracket of the same type.

public class Exercise20 {
    private static final String INPUT = "()";
    // private static final String INPUT = "()[]{}"; // True
    // private static final String INPUT = "{[()]}"; // True
    // private static final String INPUT = "({)]}"; // False
    // private static final String INPUT = "((({){[))}]"; // False

    private boolean isOpeningParanthesis(String key) {
        return "(".equals(key) || "[".equals(key) || "{".equals(key);
    }

    private boolean match(String opening, String closing) {
        return ("(".equals(opening) && ")".equals(closing)) ||
                ("[".equals(opening) && "]".equals(closing)) ||
                ("{".equals(opening) && "}".equals(closing));
    }

    private void solve() {
        Stack<String> stack = new Stack();
        for (Character character : INPUT.toCharArray()) {
            final String key = character + "";
            if (isOpeningParanthesis(key)) {
                stack.push(key);
            } else {
                String popped = stack.pop();
                if (!match(popped, key)) {
                    System.out.println("False");
                    return;
                }
            }
        }
        System.out.println("True");
    }

    public static void main(String args[]) {
        new Exercise20().solve();
    }
}