CODEWITHSUNDEEP
javastringalgorithmdata-structures
Ramanuja Sreenidhi
Ramanuja Sreenidhi

Reputation: 11

Can source string be converted to destination string?

Is there a sequence of transformation steps to convert given source string to destination string?

Note: At every step, one character can be transformed (replacement should be a character between 'A'-'Z') and all the occurrences of that character have to be transformed. Examples are given below.

Source: "ABA" 
Dest: "BAB" 
Output: True 
Explanation: ABA -> A**C**A -> **B**C**B** -> B**A**B 

Source: "AA" 
Dest: "BC" 
Output: False 
Explanation: AA -> BB

I think HashMap works. But is there another Data Structure where I don't go about comparing Character by Character?

Upvotes: 0

Views: 444

Answers (3)

Suyash Krishna
Suyash Krishna

Reputation: 241

You basically have to check that in both the strings, how many characters are repeated how many times. Kindly check whether the below logic works

 1. Declare two arrays of size equal to the length of the string (suppose N). (The length 
    of both the strings must be equal first of all). This array stores the number of 
    characters which are repeated once,twice,thrice...N times

 2. Traverse the strings and calculate the frequency of each character. Sorting the 
    strings beforehand might help.

 3. On getting the frequency of one character in a particular string, update the array 
    corresponding to that string. 

 4. Set array[newly found frequency] += 1;

 5. Repeat steps 3-4 for both the strings. After this is done for both the strings, we 
    have two arrays containing the information about how many characters are repeated how 
    many times in both the strings.

 6. Next step is to match both the arrays. If they match return True else False.

I will explain the above steps with your example:

Source: ABA
Dest: BAB

Arrays would be: arr1[3]={0,0,0} and arr2[3]={0,0,0}

(storing nummber of characters with frequency n in arr[n-1])

In string 1: Characters with 2 repetitions: 1 (A) so- arr1[2-1]+=1; 
             Characters with 1 repetition: 1 (B)  so- arr1[1-1]+=1;

arr1= {1,1,0}

In string 2: Characters with 2 repetitions: 1 (B) so- arr2[2-1]+=1;
             Characters with 1 repetition: 1 (A)  so- arr2[1-1]+=1;

arr2= {1,1,0}

As arr1 and arr2 match, the strings are convertible.

Hope this helps :)

Upvotes: 0

Devkinandan Chauhan
Devkinandan Chauhan

Reputation: 1935

It should return true if Both strings should having the same length and same chars(not the same as we are going to transform) occurrence counts.

Please check whether below approach works:

  1. check the length of both strings is the same.
  2. Get counts of all chars of source and destination strings.
  3. Sort both counts data and iterate over both, return false if you find different count at the same index.
  4. Else return true.

Upvotes: 0

talex
talex

Reputation: 20544

You can try this:

private static boolean test(String s1, String s2) {

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

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

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

        if (map.containsKey(c1)) {
            if (!map.get(c1).equals(c2)) {
                return false;
            }
        } else {
            map.put(c1, c2);
        }
    }
    return map.size() < 26;
}

Upvotes: 1

Related Questions