current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite

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;
}
share|improve this question
3  
Can you add examples of isomorphic and non-isomorphic strings, and why? That would make the question clearer. – Simon Forsberg♦ May 20 '15 at 22:43
1  
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 – Rohit Katyal May 21 '15 at 5:37
up vote 5 down vote accepted

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;       
}
share|improve this answer
up vote 4 down vote

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;
share|improve this answer
    
it still did not pass the time-efficiency test, but this is the most elegant Solution . Thanks for the tips – Rohit Katyal May 21 '15 at 5:33
    
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. – janos♦ May 21 '15 at 6:39
up vote 1 down vote

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.

share|improve this answer
    
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. – JS1 May 21 '15 at 0:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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