Сложность времени для изоморфных струн - PullRequest
Новая
       50

Сложность времени для изоморфных струн

0 голосов
/ 26 января 2019

Какова временная сложность HashMap.containsValue() и, следовательно, кода? Это O(n2) или условие if уменьшает сложность HashMap.containsValue() до O(1)? 

public static boolean isIsomorphic (String s1 , String s2){

    if (s1 == null || s2 == null){
        throw new IllegalArgumentException();
    }

    if (s1.length() != s2.length()){
        return false;
    }

    HashMap<Character, Character> map = new HashMap<>();

    for (int i = 0 ; i < s1.length(); i++){

        if (!map.containsKey(s1.charAt(i))){

            if(map.containsValue(s2.charAt(i))){

                return false;
            }           

            else{
                map.put(s1.charAt(i), s2.charAt(i));
            }           
        }
        else{
            if( map.get(s1.charAt(i)) != s2.charAt(i)){
                return false;                   
            }               
        }           
    }
    return true;        
}

1 Ответ

0 голосов
/ 26 января 2019

содержит значение сложности времени (), которое будет равно O (n + k) [n - нет.значений и к нет.ключей.Поскольку каждое значение присутствует внутри блока, элемент управления переходит к каждому блоку, а затем перемещается внутри блока до тех пор, пока не найдет значение.

...