Check Equations

Moderate
0/80
profile
Contributed by
6 upvotes

Problem statement

You are given a list of comparison equations, where each equation is in the form of “a!=b” or “a==b”. Your task is to check if all the equations satisfy or not and print the boolean value accordingly. Note: 
All the variables in the equations are lower case English alphabets.
For Example: 
You are given ‘equations’ = [‘a==b’, ‘a==c’, ‘b!=c’], here ‘a’ is equal to ‘b’ and ‘c’ so by associative law ‘b’, and ‘c’ must be equal, but it is given ‘b!=c’. Hence all the equations do not hold. Therefore the answer is False.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first input line contains a single integer ‘T’, representing the number of test cases.

The first line of input contains ‘N’ representing the number of strings.

The following ‘N’ lines each contain a string representing a string in the equations array.
Output Format: 
For each test case, print ‘True’ or ‘False’, representing if all the equations satisfy or not.

For each test case, print a separate line.
Constraints: 
1 <= T <= 10
1 <= |equations| <= 10000
|equations[i]| = 4     

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
3
a==b 
a==c 
a!=c
3
a==b 
b==c 
c==d
Sample Output 1:
False
True
Explanation:
For the first test case, ‘equations’ = [‘a==b’, ‘a==c’, ‘b!=c’], here ‘a’ is equal to ‘b’ and ‘c’ so by associative law ‘b’, and ‘c’ must be equal, but it is given ‘b!=c’. Hence all the equations do not hold. Therefore the answer is False.

For the second test case,  ‘equations’ = [‘a==b’, ‘b==c’, ‘c==d’], here ‘a’ is equal to ‘b’ and  ‘b’ is equal to ‘c’, and ‘c’ is equal to ‘d’. Hence all the equations do hold. Therefore the answer is True.
Sample Input 2:
2
2
a==b 
b==b
2
a!=b 
b!=a
Sample Output 2:
True
True
Hint

Try to make a graph from the equations

Approaches (2)
DFS

In this approach, we will make a graph out of equations, we will add an edge between two nodes if there exists and the ‘==’ sign between them. This will make all the equal elements in the same components of the graph and all the unequal in different components.

 

The for each equation we have a ‘!=’ between nodes, we check using DFS if it’s possible to reach one node from the other. 

 

We create a DFS(x, y, adj, visited), where y is the node from which we are checking if it’s possible to reach x, adj is the adjacency list of the graph we formed, and visited is the set of all the visited nodes.

Algorithm:

  • In the function DFS(x, y, adj, visited):
    • If x is in adj[y], return True
    • Iterate child through adj[y]:
      • If child not in visited, insert child is in visited
      • If dfs(x, child, adj, visited) is True, then return True
    • Return False

 

  • Create an empty adjacency list adj.
  • Iterate eqn through equations:
    • Set x, op and y as the first character, the next two characters and the last character of eqn, respectively.
    • If op is equal to ‘==’, then,
      • Insert y into adj[x] and x into adj[y]
  • Iterate eqn through equations:
    • Set x, op and y as the first character, the next two characters and the last character of eqn, respectively.
    • If op is equal to ‘!=’, then
      • If x is equal to y, return False
      • If dfs(x, y, adj, empty set) is True
        • Return False
  • Return True
Time Complexity

O(N^2), Where N is the number of equations. 

 

We are iterating over each equation of the graph, which will cost O(N), then a DFS operation on a graph costs O(E + V); in this case, E = N and V is at most 26. Hence the time complexity for DFS is O(N), Hene the final time complexity is O(N^2).

Space Complexity

O(1),

 

We are maintaining an adjacency list that will take O(1) space since we will have a maximum of 26 nodes. The space complexity of DFS will also be O(1). Hence the final space complexity is O(1).

Code Solution
(100% EXP penalty)
Check Equations
Full screen
Console