Ambigram Detection- Google Top Interview Questions
Problem Statement :
You are given a lowercase alphabet string s and a two-dimensional list of strings pairs.
Each element in pairs contains [a, b] meaning that character a and b are considered equivalent.
We say that if a and b are equivalent and b and c are equivalent, then a and c are also equivalent.
Also, any character a is equivalent to itself.
Return whether s is a palindrome given the equivalence relations.
Constraints
0 ≤ n ≤ 100,000 where n is the length of s
0 ≤ p ≤ 100,000 where p is the length of p
Example 1
Input
s = "acba"
pairs = [
["b", "c"]
]
Output
True
Explanation
Since "b" = "c", we have "acba" = "acca", which is a palindrome.
Example 2
Input
s = "zz"
pairs = []
Output
True
Explanation
"z" is equivalent to itself.
Example 3
Input
s = "ac"
pairs = [
["a", "b"],
["b", "c"]
]
Output
True
Explanation
Since "a" = "c", we have "ac" = "cc", which is a palindrome.
Solution :
Solution in C++ :
bool solve(string s, vector<vector<string>>& pairs) {
vector<int> parent(26);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
};
auto join = [&](int a, int b) { parent[find(a)] = parent[find(b)]; };
for (auto& p : pairs) {
int a = p[0][0] - 'a';
int b = p[1][0] - 'a';
join(a, b);
}
for (char& c : s) {
int i = c - 'a';
c = find(i) + 'a';
}
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] ^ s[j]) return false;
i++, j--;
}
return true;
}
Solution in Java :
import java.util.*;
class Solution {
public boolean solve(String s, String[][] pairs) {
DisjointSetUnion dsu = new DisjointSetUnion(26);
for (String[] p : pairs) {
int a = p[0].charAt(0) - 'a';
int b = p[1].charAt(0) - 'a';
dsu.connect(a, b);
}
for (int i = 0; i < s.length(); i++) {
int j = s.length() - 1 - i;
int a = s.charAt(i) - 'a';
int b = s.charAt(j) - 'a';
if (!dsu.connected(a, b))
return false;
}
return true;
}
static class DisjointSetUnion {
public int[] parent;
public int[] weight;
public int count;
public DisjointSetUnion(int N) {
count = N;
parent = new int[N];
for (int i = 0; i < N; i++) parent[i] = i;
weight = new int[N];
Arrays.fill(weight, 1);
}
//"find"
public int root(int p) {
if (p == parent[p])
return p;
return parent[p] = root(parent[p]);
}
//"union"
public void connect(int p, int q) {
p = root(p);
q = root(q);
if (p == q)
return;
if (weight[p] < weight[q]) {
parent[p] = q;
weight[q] += weight[p];
} else {
parent[q] = p;
weight[p] += weight[q];
}
count--;
}
public boolean connected(int p, int q) {
return root(p) == root(q);
}
}
}
Solution in Python :
class Solution:
def solve(self, s, pairs):
parent = {}
for c in s:
parent[c] = c
def find(c):
if c not in parent or parent[c] == c:
return c
parent[c] = find(parent[c])
return parent[c]
def union(a, b):
a = find(a)
b = find(b)
if a != b:
parent[b] = a
for s1, e1 in pairs:
union(s1, e1)
s = [find(x) for x in s]
return s == s[::-1]
View More Similar Problems
2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →