1
\$\begingroup\$

Two strings are isomorphic if the characters in s can be replaced to get t. Can efficiency be increased further for this code? As I am getting errors that limit is being exceeded for very large strings.

static boolean isIsomorphic(String s, String t) {

s= s.toLowerCase();
t = t.toLowerCase();
if(s.length()!=t.length()){
    return false;
}
if(s.equalsIgnoreCase(t)){
    return true;
}
    HashMap<Character,Integer> mapOfFirst = new HashMap<Character,Integer>();
    HashMap<Character,Integer> mapOfSec = new HashMap<Character,Integer>();
    int cnt1 =0 ;
    int cnt2 =0 ;
    for(int i =0;i<s.length();i++){

        if(mapOfFirst.get(s.toCharArray()[i])!=null){

        }
        else{
            mapOfFirst.put(s.toCharArray()[i],cnt1);
            cnt1 = cnt1+1;
        }

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

        if(mapOfSec.get(t.toCharArray()[i])!=null){

        }
        else{
            mapOfSec.put(t.toCharArray()[i],cnt2);
            cnt2 = cnt2+1;
        }

    }

    char[] sCharArray_Fir = s.toCharArray();
    char[] sCharArray_Sec= t.toCharArray();

    for(int i = 0 ; i< s.length();i++){
        int ch1 = mapOfFirst.get(sCharArray_Fir[i]);
        int ch2 = mapOfSec.get(sCharArray_Sec[i]);
        if(ch1!=ch2){
            return false;
        }
    }

    return true;
}   
\$\endgroup\$
  • 3
    \$\begingroup\$ Can you add examples of isomorphic and non-isomorphic strings, and why? That would make the question clearer. \$\endgroup\$ – Simon Forsberg May 20 '15 at 22:43
  • 1
    \$\begingroup\$ Examples isomorphic and non-isomorphic strings , "title" and "paper" are isomorphic as t can be mapped to p , i to a , l to e , e to r . "race" ,"hello" this can not be isomorphic \$\endgroup\$ – Rohit Katyal May 21 '15 at 5:37
5
\$\begingroup\$

The efficiency could be increased if you place

char[] sCharArray_Fir = s.toCharArray();
char[] sCharArray_Sec= t.toCharArray();

before your for loops and replace every

s.toCharArray()[i]

with

sCharArray_Fir[i]

The same applies tot.toCharArray()[i].
Each time you call that, your string is converted to char array.
Call it once before the for loops.

Also, consider removing the if conditional, and fill your maps first instead of checking them for mappings while they're empty:

for(int i =0;i<s.length();i++){
    // if(mapOfFirst.get(s.toCharArray()[i])!=null){
    //
    // }
    // else{
        mapOfFirst.put(sCharArray_Fir[i],cnt1);
        cnt1 = cnt1+1;
    // }
}

Another thing is that you already checked if your strings are of the same length, so you can include contents of your second for loop in the first one (use the same cnt value too):

for(int i =0;i<s.length();i++){
    mapOfFirst.put(sCharArray_Fir[i],cnt1);
    mapOfSec.put  (sCharArray_Sec[i],cnt1);
    cnt1 = cnt1+1;       
}
\$\endgroup\$
4
\$\begingroup\$

Oh boy. Doesn't this look a bit suspicious?

for(int i =0;i<s.length();i++){
    if(mapOfFirst.get(s.toCharArray()[i])!=null){

What do you think happens when you call .toCharArray on a String? Take a look at the source code.

s.toCharArray() allocates a new char[s.size()] every time it's called. In your case, that's in every loop cycle, sometimes more than once. That can't be good.

If you replace all the .toCharArray()[i] calls with .charAt(i), it might actually already become fast enough.

Another weakness of the algorithm is that you build up two complete maps of character positions of both strings before iterating over the characters of the first string. You could iterate just once, track the consistency of the mapping, and short-circuit as soon as an inconsistent mapping is found.

    Map<Character, Character> mapping = new HashMap<>();
    Set<Character> used = new HashSet<>();

    for (int i = 0; i < s.length(); ++i) {
        char cs = s.charAt(i);
        char ct = t.charAt(i);
        Character ms = mapping.get(cs);
        if (ms == null) {
            if (used.contains(ct)) {
                return false;
            }
            used.add(ct);
            mapping.put(cs, ct);
        } else {
            if (!ms.equals(ct)) {
                return false;
            }
        }
    }
    return true;
\$\endgroup\$
  • \$\begingroup\$ it still did not pass the time-efficiency test, but this is the most elegant Solution . Thanks for the tips \$\endgroup\$ – Rohit Katyal May 21 '15 at 5:33
  • \$\begingroup\$ Oh really? In that case, this can be further optimized to make it faster, by using a boolean[] instead of the Set, and a char[] instead of the Map, at the expense of using more space. The boolean[] and char[] can be initialized with the size of the alphabet, and the indexes can be derived from the int value of the characters in the input strings. \$\endgroup\$ – Stop ongoing harm to Monica May 21 '15 at 6:39
1
\$\begingroup\$

Oh boy. Doesn't this look a bit suspicious?

    if(mapOfFirst.get(s.toCharArray()[i])!=null){

    }
    else{

What do you think happens if you see the same character more than once? Nothing, or Something?

Your code only works correctly if each character in the input strings are unique.

\$\endgroup\$
  • \$\begingroup\$ I think the program still works. Repeat characters do not need to modify to the map because the map contains a unique id for each first occurrence of a character. I haven't run the program yet but in my mind it makes sense. \$\endgroup\$ – JS1 May 21 '15 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.