fork download

copy

struct TrieNode {
	TrieNode* child[26];
	int idx;
	vector<int>pal;
 
	TrieNode() {
		for (int i = 0; i<26; i++) {
			child[i] = nullptr;
		}
		idx = -1;
	}
};
 
class Trie {
	private:
	TrieNode* par;
	bool check(string &t, int i) {
		int n = t.size();
		int st = i;
		int end = n - 1;
		while (st <= end) {
			if (t[st] != t[end]) {
				return false;
			}
			st++;
			end--;
		}
		return true;
	}
 
	public:
	Trie() {
		par = new TrieNode();
	}
 
	void insert(string &s, int ind) {
		int n = s.size();
		TrieNode* node = par;
		for (int i = 0; i<n; i++) {
			int ch = s[i]-'a';
			if (check(s, i)) {
				node->pal.push_back(ind);
			}
			if (node->child[ch] == nullptr) {
				node->child[ch] = new TrieNode();
			}
			node = node->child[ch];
		}
		node->idx = ind;
		node->pal.push_back(ind);
	}
 
	bool isValid(string &s, int ind) {
		int n = s.size();
		TrieNode*node = par;
 
		for (int i = 0; i<n; i++) {
			// if taht end is not presnet
			// if there is end ther the we can check for the remaining sequence is tahta  pal
			int ch = s[i]-'a';
			if (node->idx != -1 && check(s, i) && node->idx != ind) {
				return true;
			}
			if (node->child[ch] == nullptr) {
				return false;
			}
			node = node->child[ch];
 
		}
		for (auto &x:node->pal) {
			if (x != ind)return true;
		}
		return false;
	}
};
class Solution {
	public:
	bool palindromePair(vector<string>& arr) {
		// Code here
		int n = arr.size();
		if (n <= 1)return false;
		// we have top find atleat one pair where
		// if oi joined that two it becomes palindrome
		// size wont matter
		// we can use trie i guess
		// first we have to insert all thekement sinto the trie
		// na an first we haver to reverse the  word and check if that is prenst or not
		// ansd if there eneds a word means it is true//otherwise we have to check
		// s o we have to push the smaller elemsnts
		// so that when it fully compares means remaing we can check if remaing sequence is a p
		// if tahasts a pal return true;
 
		Trie trie;
 
		for (int i = 0; i<n; i++) {
 
			trie.insert(arr[i], i);
		}
 
		for (int i = 0; i<n; i++) {
			string t = arr[i];
			reverse(t.begin(), t.end());
			if (trie.isValid(t, i)) {
				return true;
			}
		}
		return false;
 
	}
};
 

prog.cpp:4:2: error: ‘vector’ does not name a type
  vector<int>pal;
  ^~~~~~
prog.cpp:17:13: error: ‘string’ has not been declared
  bool check(string &t, int i) {
             ^~~~~~
prog.cpp:36:14: error: ‘string’ has not been declared
  void insert(string &s, int ind) {
              ^~~~~~
prog.cpp:53:15: error: ‘string’ has not been declared
  bool isValid(string &s, int ind) {
               ^~~~~~
prog.cpp: In member function ‘bool Trie::check(int&, int)’:
prog.cpp:18:13: error: request for member ‘size’ in ‘t’, which is of non-class type ‘int’
   int n = t.size();
             ^~~~
prog.cpp:22:12: error: invalid types ‘int[int]’ for array subscript
    if (t[st] != t[end]) {
            ^
prog.cpp:22:22: error: invalid types ‘int[int]’ for array subscript
    if (t[st] != t[end]) {
                      ^
prog.cpp: In member function ‘void Trie::insert(int&, int)’:
prog.cpp:37:13: error: request for member ‘size’ in ‘s’, which is of non-class type ‘int’
   int n = s.size();
             ^~~~
prog.cpp:40:16: error: invalid types ‘int[int]’ for array subscript
    int ch = s[i]-'a';
                ^
prog.cpp:42:11: error: ‘struct TrieNode’ has no member named ‘pal’
     node->pal.push_back(ind);
           ^~~
prog.cpp:50:9: error: ‘struct TrieNode’ has no member named ‘pal’
   node->pal.push_back(ind);
         ^~~
prog.cpp: In member function ‘bool Trie::isValid(int&, int)’:
prog.cpp:54:13: error: request for member ‘size’ in ‘s’, which is of non-class type ‘int’
   int n = s.size();
             ^~~~
prog.cpp:60:16: error: invalid types ‘int[int]’ for array subscript
    int ch = s[i]-'a';
                ^
prog.cpp:70:22: error: ‘struct TrieNode’ has no member named ‘pal’
   for (auto &x:node->pal) {
                      ^~~
prog.cpp: At global scope:
prog.cpp:78:22: error: ‘vector’ has not been declared
  bool palindromePair(vector<string>& arr) {
                      ^~~~~~
prog.cpp:78:28: error: expected ‘,’ or ‘...’ before ‘<’ token
  bool palindromePair(vector<string>& arr) {
                            ^
prog.cpp: In member function ‘bool Solution::palindromePair(int)’:
prog.cpp:80:11: error: ‘arr’ was not declared in this scope
   int n = arr.size();
           ^~~
prog.cpp:101:4: error: ‘string’ was not declared in this scope
    string t = arr[i];
    ^~~~~~
prog.cpp:101:4: note: suggested alternative: ‘trie’
    string t = arr[i];
    ^~~~~~
    trie
prog.cpp:102:12: error: ‘t’ was not declared in this scope
    reverse(t.begin(), t.end());
            ^
prog.cpp:102:4: error: ‘reverse’ was not declared in this scope
    reverse(t.begin(), t.end());
    ^~~~~~~

Standard output is empty