1/12/21 Hashmap palindrome

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code" Output: false

Example 2:

Input: "aab" Output: true

Example 3:

Input: "carerac" Output: true

 

내가 적은 답안.. Hashmap으로 구현하려고 했는데..

class Solution {
    public boolean canPermutePalindrome(String s) {
        
        // Creating a HashMap containing char 
        // as a key and occurrences as  a value 
        HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>(); 
  
        // Converting given string to char array 
  
        char[] strArray = inputString.toCharArray(); 
        boolean result = false;
        
        // checking each char of strArray 
        for (char c : strArray) { 
            if (charCountMap.containsKey(c)) { 
  
                // If char is present in charCountMap, 
                // incrementing it's count by 1 
                charCountMap.put(c, charCountMap.get(c) + 1); 
            } 
            else { 
  
                // If char is not present in charCountMap, 
                // putting this char to charCountMap with 1 as it's value 
                charCountMap.put(c, 1); 
            } 
        } 
        
        // when s.length = odd number, each character occurs even number of times except the last character
        if (s.length % 2 = 1){
            //if s.length = odd number
            
        }
        
        // when s.length = even number, each chracter occurs even number of times
        
        return result;
    }
}

정답

 

From the discussion above, we know that to solve the given problem, we need to count the number of characters with odd number of occurrences in the given string ss. To do so, we can also make use of a hashmap, \text{map}map. This \text{map}map takes the form (\text{character}, \text{number of occurrences of character})(character,number of occurrences of character).

We traverse over the given string ss. For every new character found in ss, we create a new entry in the \text{map}map for this character with the number of occurrences as 1. Whenever we find the same character again, we update the number of occurrences appropriately.

At the end, we traverse over the \text{map}map created and find the number of characters with odd number of occurrences. If this \text{count}count happens to exceed 1 at any step, we conclude that a palindromic permutation isn't possible for the string ss. But, if we can reach the end of the string with \text{count}count lesser than 2, we conclude that a palindromic permutation is possible for ss.

The following animation illustrates the process.

 

public class Solution {
 public boolean canPermutePalindrome(String s) {
     HashMap < Character, Integer > map = new HashMap < > ();
     for (int i = 0; i < s.length(); i++) {
         map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
     }
     int count = 0;
     for (char key: map.keySet()) {
         count += map.get(key) % 2; // 나머지들을 다 더해서 1이하로 나오면(하나만 갯수가 홀수인 거라면)
     }
     return count <= 1;
 }
}

 

** Hashmap

 

HashMap 이란?

 

Java Collections Framework에 속한 구현체 클래스이면서, Map 인터페이스를 구현한 함수이다. 
따라서 데이터의 저장은 key, value 형태가 된다.  key 값의 hashCode를 index로 Araay에 값을 저장한다. 따라서 검색속도는 매우 빠르다.
그리고 해싱(Hashing) 검색을 사용하기 때문에 대용량 데이터 관리에도 좋은 성능을 보여주고 있다. 
key 값은 중복이 되지 않고, value 값은 허용이 된다.

 

HashMap 에서 데이터를 넣는 방법은 put() 함수를 사용한다. 첫번째 인수로 key 값을 넣고, 두번째 인수로 value 를 입력한다.

 

**CharAt with For loop

//This will return the first char of the string

char ch1 = str.charAt(0);

 

The getOrDefault(Object key, V defaultValue) method of Map interface, implemented by HashMap class is used to get the value mapped with specified key. If no value is mapped with the provided key then the default value is returned.