String Isomorphism - Amazon Top Interview Questions


Problem Statement :


Given lowercase alphabet strings s, and t return whether you can create a 1-to-1 mapping for each letter in s to another letter (could be the same letter) such that s could be mapped to t, with the ordering of characters preserved.

Constraints

n ≤ 100,000 where n is the length of s
m ≤ 100,000 where m is the length of t


Example 1

Input
s = "coco"
t = "kaka"


Output
True


Explanation
We can create this mapping:

"c" -> "k"
"o" -> "a"


Example 2

Input
s = "cat"
t = "foo"

Output
False


Explanation
We can't transform both "a" and "t" into "o" since it has to be a 1-to-1 mapping.




Example 3
Input
s = "hello"
t = "hello"

Output
True


Explanation
The mapping can just map each letter to itself.


Solution :



title-img 




                        Solution in C++ :

bool solve(string s, string t) {
    unordered_map<char, char> st, ts;

    if (s.size() != t.size()) return 0;

    for (int i = 0; i < s.size(); i++) {
        // check the s -> t mapping
        if (not st.count(s[i]) or st[s[i]] == t[i])
            // this is the first time I've seen this char in s,
            // or second time with the same mapped value as last time
            st[s[i]] = t[i];
        else
            return false;

        // check the t -> s mapping (same logic as above)
        if (not ts.count(t[i]) or ts[t[i]] == s[i])
            ts[t[i]] = s[i];
        else
            return false;
    }

    return true;
}
                    


                        Solution in Java :

import java.util.*;

class Solution {
    public boolean solve(String s, String t) {
        if (s == t)
            return true;
        if (s.length() != t.length())
            return false;
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i)))
                return false;
        }
        return true;
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def solve(self, s, t):
        ds, dt = {}, {}
        for i in range(len(s)):
            if s[i] not in ds:
                ds[s[i]] = t[i]
            else:
                if ds[s[i]] != t[i]:
                    return False
            if t[i] not in dt:
                dt[t[i]] = s[i]
            else:
                if dt[t[i]] != s[i]:
                    return False
        return True


View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →