One map O(n) Java


  • 0
    L

    Just use one map to do it.

    Map<Character,Character> map = new HashMap<Character,Character>();
    int len = 0;
    while (len < s.length()) {
        if (map.containsKey(s.charAt(len)) && map.get(s.charAt(len)) != t.charAt(len)) {
            return false;
        } else if (!map.containsKey(s.charAt(len)) && map.containsValue(t.charAt(len))){
            return false;
        }
        map.put(s.charAt(len), t.charAt(len));
        len++;
    }
    return true;

  • 0

    What's the runtime complexity of map.containsValue?


  • 0
    B

    I see into jdk1.7 code, map.containsValue() will check all the entries, so is an O(n) time operation.


  • 0
    K

    map.containsValue() is O(n), I don't think time complexity of this solution is O(n).


Log in to reply
 

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