Trie | (Insert and Search)

Trie is an efficient information retrieval data structure. Use this data structure to store Strings and search strings. Your task is to use TRIE data structure and search the given string A. If found print 1 else 0.

Example 1:

Input:
N = 8
key[] = {the,a,there,answer,any,by,
         bye,their}
search = the
Output: 1
Explanation: the is present in the given
string "the a there answer any by bye
their"

Example 2:

Input:
N = 8
key[] = {the,a,there,answer,any,by,
         bye,their}
search = geeks
Output: 0
Explanation: geeks is not present in the
given string "the a there answer any by
bye their"

Your Task:
Complete insert and search function and return true if key is present in the formed trie else false in the search function. (In case of true, 1 is printed and false, 0 is printed by the driver's code.

Expected Time Complexity: O(M+|search|).
Expected Auxiliary Space: O(M).
M = sum of the length of all strings which is present in the key[] 

|search| denotes the length of the string search.

Answer:





for i in range(t):

    n= int(input())

    s= input()

    s.split()

    f= input()

    l= s.split()

    flag=0

    for k in l:

        if(k==f):

            flag=1

            break

    print(flag)

        


for i in range(n):

    no=int(input())

    inp=input().split()

    inp1=input()

    if inp1 in inp:

        print(1)

    else:

        print(0)        


Comments

Post a Comment

Popular posts from this blog

Large Factorial of array

You are given an array   A   of integers of length   N . You need to calculate factorial of each number. The answer can be very large, so print it modulo   10 9  + 7 .   Example 1: Input: N = 5 A[] = {0, 1, 2, 3, 4} Output: 1 1 2 6 24 Explanation: Factorial of 0 is 1, factorial of 1 is 1, factorial of 2 is 2,  factorial of 3 is 6 and so on. Example 2: Input: N = 3 A[] = {5, 6, 3} Output: 120 720 6 Explanation: Factorial of 5 is 120, factorial of 6 is 720,  factorial of 3 is 6. Your Task: Complete the function  factorial()  which takes   list  a  and single integer  n , as input parameters and returns a list of factorials of the numbers in the list a.
Read more

LEARN SOMMETHING INTRESTING

  Yeah, I love Python one-liners. Let us break it down. input()   This is used to fetch input from the user. In this case. We are expecting the user to provide a list of integers. How do I know? Look next. input().strip()   This will eliminate trailing spaces from the user input, if they are there. Why is it required? Because some users will do that and that might break your program. Remember that input() will cast the input as string. So, now we have a string of integers like so: “1 2 4 42” input.strip().split()   split() is used to create a Python list out of a string. If no delimiter is given, this breaks the string by spaces. So, now we have: [“1”, “2”, “4”, “42”] map(int, input().strip().split())   map() takes two arguments. The first one is the method to apply, the second one is the data to apply it to. By this understanding, we can see this is doing nothing but typecasting every element of the list to an integer value. Since map returns the data type it w...
Read more

Largest Element in Array

  Given an array A[] of size n . The task is to find the largest element in it.   Example 1: Input: n = 5 A[] = {1, 8, 7, 56, 90} Output: 90 Explanation: The largest element of given array is 90.   Example 2: Input:   n = 7 A[] = {1, 2, 0, 3, 2, 4, 5} Output: 5 Explanation: The largest element of given array is 5.    def largest( arr, n):     return max(arr) #{ #  Driver Code Starts #Initial Template for Python 3 def main():     T = int(input())     while(T > 0):         n = int(input())         a = [int(x) for x in input().strip().split()]         print(largest(a, n))         T -= 1 if __name__ == "__main__":     main()    
Read more