Java da iki Stringin Denkşekilliliği (Isomorphism)

Posted by dogukanhan on August 27, 2017 · 1 min read

Başlamadan önce burada Sadi Evren Şeker Hocamızın Isomorphism üzerine güzel bir yazısı bulunmakta link üzerinden okuyabilirsiniz.

http://bilgisayarkavramlari.sadievrenseker.com/2009/06/18/denksekillilik-isomorphism/

Girilen iki tane s ve t String değişkenleri olarak adlandıralım, isomorphic olup olmadığına karar veren algoritma. S deki karakterler yerine başka karakterler konulup t elde edilebiliyorsa bunlar isomorphic’tir.

Örnek olarak

“egg” ve  “add” isomorphic’tir, e karekteri yerine a ve g karekteri yerine d yi değiştirirsek ikinci Stringi oluşturabiliriz.” foo” ve “bar” ise isomorphic değildir. Çünkü o karekteri hem a hemde r karakterlerine denk gelmektedir ikinci String’i oluşturmanın bir yolu yoktur.

public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null) {
            return false;
        }

        if (s.length() != t.length()) {
            return false;
        }

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

        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);

            if (map.containsKey(c1)) {
                if (map.get(c1) != c2)
                {
                    return false;
                }
            } else {
                if (map.containsValue(c2)) 
                {
                    return false;
                }
                map.put(c1, c2);
            }
        }

        return true;
    }

Zaman O(n) dir.

Kaynak: https://www.programcreek.com/2014/05/leetcode-isomorphic-strings-java/