{"id":159,"date":"2022-03-05T19:53:10","date_gmt":"2022-03-06T00:53:10","guid":{"rendered":"https:\/\/sites.temple.edu\/vahid\/?p=159"},"modified":"2022-03-05T19:53:11","modified_gmt":"2022-03-06T00:53:11","slug":"hackerrank-solutions-no-prefix-set","status":"publish","type":"post","link":"https:\/\/sites.temple.edu\/vahid\/2022\/03\/05\/hackerrank-solutions-no-prefix-set\/","title":{"rendered":"HackerRank Solutions: No Prefix Set"},"content":{"rendered":"\n

Problem<\/strong><\/p>\n\n\n\n

There is a given list of strings where each string contains only lowercase letters from , inclusive. The set of strings is said to be a GOOD SET<\/strong> if no string is a prefix of another string. In this case, print GOOD SET<\/strong>. Otherwise, print BAD SET<\/strong> on the first line followed by the string being checked.<\/p>\n\n\n\n

Note<\/strong> If two strings are identical, they are prefixes of each other.<\/p>\n\n\n\n

Example<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Here ‘abcd’ is a prefix of ‘abcde’ and ‘bcd’ is a prefix of ‘bcde’. Since ‘abcde’ is tested first, print<\/p>\n\n\n\n

BAD SET  \nabcde\n<\/code><\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
No string is a prefix of another so print<\/p>\n\n\n\n
GOOD SET \n<\/code><\/pre>\n\n\n\n
Function Description<\/strong>
Complete the noPrefix<\/em> function in the editor below.<\/p>\n\n\n\n
noPrefix<\/em> has the following parameter(s):
– string words[n]:<\/em> an array of strings<\/p>\n\n\n\n
Prints<\/strong>
– string(s):<\/em> either GOOD SET<\/strong> or BAD SET<\/strong> on one line followed by the word on the next line. No return value is expected.<\/p>\n\n\n\n
Input Format<\/strong>
First line contains , the size of .
Then next  lines each contain a string, .<\/p>\n\n\n\n
Constraints<\/strong>

 the length of words[i] 
All letters in  are in the range ‘a’ through ‘j’, inclusive.<\/p>\n\n\n\n
Sample Input00<\/strong><\/p>\n\n\n\n
STDIN       Function\n-----       --------\n7            words[] size n = 7\naab          words = ['aab', 'defgab', 'abcde', 'aabcde', 'bbbbbbbbbb', 'jabjjjad']\ndefgab  \nabcde\naabcde\ncedaaa\nbbbbbbbbbb\njabjjjad\n<\/code><\/pre>\n\n\n\n
Sample Output00<\/strong><\/p>\n\n\n\n
BAD SET\naabcde\n<\/code><\/pre>\n\n\n\n
Explanation<\/strong>
‘aab’ is prefix of ‘aabcde’ so it is a BAD SET<\/strong> and fails at string ‘aabcde’.<\/p>\n\n\n\n
Sample Input01<\/strong><\/p>\n\n\n\n
4\naab\naac\naacghgh\naabghgh\n<\/code><\/pre>\n\n\n\n
Sample Output01<\/strong><\/p>\n\n\n\n
BAD SET\naacghgh\n<\/code><\/pre>\n\n\n\n
Explanation<\/strong>
‘aab’ is a prefix of ‘aabghgh’, and aac’ is prefix of ‘aacghgh’. The set is a\u00a0BAD SET<\/strong>. ‘aacghgh’ is tested before ‘aabghgh’, so and it fails at ‘aacghgh’.<\/p>\n\n\n\n
Solution<\/strong><\/p>\n\n\n\n
#!\/bin\/python3\r\n\r\nimport math\r\nimport os\r\nimport random\r\nimport re\r\nimport sys\r\n\r\n#\r\n# Complete the 'noPrefix' function below.\r\n#\r\n# The function accepts STRING_ARRAY words as parameter.\r\n#\r\n\r\nclass Node:\r\n    def __init__(self, parent=None, childrean=dict()):\r\n        self.parent = parent\r\n        self.children = childrean\r\n        self.leaf = False\r\n\r\ndef noPrefix(words):\r\n    # Write your code here\r\n    # make Trie\r\n    root = Node(None)\r\n    for word in words:\r\n        node = root\r\n        prefix = False\r\n        for let in word:\r\n            exists = []\r\n            if let in node.children.keys():\r\n                child = node.children[let]\r\n                exists.append(True)\r\n            else:\r\n                exists.append(False)\r\n                child = Node(node, dict())\r\n                node.children[let] = child\r\n            node = child\r\n            if node.leaf:\r\n                prefix = True\r\n                break\r\n        if prefix | all(exists):\r\n            prefix = True\r\n            break\r\n        node.leaf = True\r\n    if prefix:\r\n        print('BAD SET')\r\n        print(word)\r\n    else:\r\n        print('GOOD SET')\r\n            \r\n    \r\n    \r\nif __name__ == '__main__':\r\n    n = int(input().strip())\r\n\r\n    words = []\r\n\r\n    for _ in range(n):\r\n        words_item = input()\r\n        words.append(words_item)\r\n\r\n    noPrefix(words)\r<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Problem There is a given list of strings where each string contains only lowercase letters from , inclusive. The set of strings is said to be…<\/p>\n
Continue readingHackerRank Solutions: No Prefix Set<\/span><\/a><\/div>\n","protected":false},"author":18759,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[102,104,4,103],"class_list":["post-159","post","type-post","status-publish","format-standard","hentry","category-programming","tag-hackerrank","tag-programming","tag-python","tag-solution","entry"],"_links":{"self":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/posts\/159","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/users\/18759"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/comments?post=159"}],"version-history":[{"count":0,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/posts\/159\/revisions"}],"wp:attachment":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/media?parent=159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/categories?post=159"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/tags?post=159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}