Appearance
question:Problem Statement You are required to implement a class `WordDictionary` with the following functions: 1. `add_word(word)`: Adds a word to the dictionary. 2. `search(word)`: Searches for a word in the dictionary. Word can contain the '.' character which can match any letter. Your implementation should make use of a Trie and efficiently handle both exact matches and searches containing wildcards. # Input Format 1. `add_word(word)` function will be called multiple times with a string `word` consisting of lowercase English letters and having a length of 1 to 100. 2. `search(word)` function will be called multiple times with a string `word` consisting of lowercase English letters and '.' character and having a length of 1 to 100. # Output Format - For `search(word)`, return `True` if the word or pattern exists in the dictionary, otherwise return `False`. # Constraints 1. The total number of words added will not exceed `5*10^4`. 2. Wildcard character `.` in `search(word)` can replace any single letter, and words will ensure at least one non-dot character for valid searches. # Example ```python dictionary = WordDictionary() dictionary.add_word("bad") dictionary.add_word("dad") dictionary.add_word("mad") assert dictionary.search("pad") == False assert dictionary.search("bad") == True assert dictionary.search(".ad") == True assert dictionary.search("b..") == True ``` # Implementation Define the `WordDictionary` class using a Trie for efficient add and search operations, following the methods outlined. Consider edge cases and ensure performance meets the constraints.
answer:class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class WordDictionary: def __init__(self): self.root = TrieNode() def add_word(self, word): current = self.root for char in word: if char not in current.children: current.children[char] = TrieNode() current = current.children[char] current.is_end_of_word = True def search(self, word): def search_in_node(word, node): for i, char in enumerate(word): if char == '.': for child in node.children.values(): if search_in_node(word[i+1:], child): return True return False else: if char not in node.children: return False node = node.children[char] return node.is_end_of_word return search_in_node(word, self.root)
question:# Context In many applications, you may need to determine if two words or phrases are composed of the same letters in the same quantity, essentially checking if they are anagrams. This can be useful in fields like cryptography and text analysis. # Task Write a function that determines if two strings are anagrams of each other. The input strings are guaranteed to consist of lowercase English letters only. # Function Signature ```python def are_anagrams(s1: str, s2: str) -> bool: # Your code here ``` # Input * `s1`: A string of lowercase letters (1 <= len(s1) <= 100) * `s2`: A string of lowercase letters (1 <= len(s2) <= 100) # Output * Return `True` if `s1` and `s2` are anagrams, `False` otherwise. # Constraints * The function should run in O(n) time complexity, where n is the maximum length of the input strings. * Space complexity should be O(1), not considering input and output. # Examples * Example 1: - Input: s1 = "listen", s2 = "silent" - Output: True * Example 2: - Input: s1 = "apple", s2 = "pale" - Output: False # Notes * Consider edge cases such as strings of different lengths. * Performance should be efficient due to real-time application potential. > **Hint**: Think about using arrays to count occurrences of each character.
answer:def are_anagrams(s1: str, s2: str) -> bool: Returns True if s1 and s2 are anagrams, False otherwise. # Early exit if lengths differ if len(s1) != len(s2): return False # Initialize a list to count occurrences of each character count = [0] * 26 # there are 26 letters in English alphabet # Count occurrences of each character in s1 for char in s1: count[ord(char) - ord('a')] += 1 # Subtract counts according to s2 for char in s2: count[ord(char) - ord('a')] -= 1 # If all counts return to zero, the strings are anagrams return all(c == 0 for c in count)
question:# Question: Array Filtering within Specified Range You are tasked with implementing a function `limit` that filters the elements of an array, retaining only those that fall within a specified minimum and maximum limit. This function should be versatile, handling cases where only one limit is provided or neither is provided. Function Signature ```python def limit(arr: list, min_lim: int = None, max_lim: int = None) -> list: pass ``` Input - `arr` (list): A list of integers. - `min_lim` (int): The lower bound to filter values (inclusive). If `None`, consider no lower bound. - `max_lim` (int): The upper bound to filter values (inclusive). If `None`, consider no upper bound. Output - Returns a list of integers from `arr` that fall within the specified range. Constraints - The length of the array will not exceed `10^6`. - The values in the array will be between `-10^9` and `10^9`. Example ```python # Example 1: assert limit([1, 2, 3, 4, 5], None, 3) == [1, 2, 3] # Example 2: assert limit([10, 15, 20, 25, 30], 12, 28) == [15, 20, 25] # Example 3: assert limit([100, 200, 300, 400, 500], 250, None) == [300, 400, 500] # Example 4: assert limit([], None, None) == [] ``` Explanation - In the first example, `None` for `min_lim` implies no lower limit, and `3` for `max_lim` means all values must be less than or equal to 3. - In the second example, values between 12 and 28 (inclusive) are retained. - In the third example, `None` for `max_lim` implies no upper limit, so values greater than or equal to 250 are retained. - An empty array naturally returns an empty array as there are no elements to filter. Ensure your function handles edge cases and large data efficiently.
answer:def limit(arr: list, min_lim: int = None, max_lim: int = None) -> list: Filters the elements of the array, retaining only those that fall within the specified minimum and maximum limits. Parameters: arr (list): A list of integers. min_lim (int): The lower bound to filter values (inclusive). If None, consider no lower bound. max_lim (int): The upper bound to filter values (inclusive). If None, consider no upper bound. Returns: list: A list of integers from arr that fall within the specified range. if min_lim is not None and max_lim is not None: return [x for x in arr if min_lim <= x <= max_lim] elif min_lim is not None: return [x for x in arr if x >= min_lim] elif max_lim is not None: return [x for x in arr if x <= max_lim] else: return arr
question:# Truncated Mean Calculation You are given a list of numbers and a percentage. Your task is to write a function that calculates the mean of the list after removing a certain percentage of the largest and smallest values. The percentage given will be divided equally to trim the smallest and largest values. Function Signature ```python def trimmean(arr: List[float], per: float) -> float: ``` Input - `arr`: a list of floats. (1 <= len(arr) <= 10^5) - `per`: a float percentage between 0 and 100. Output - Returns a float, representing the trimmed mean of the list. Constraints - The list will contain at least one element. - The percentage will be a valid float between 0 and 100. - The number of elements to trim on both sides combined will always be rounded down to the nearest integer. Example Consider the following example to understand the requirement: ```python arr = [7, 8, 6, 9, 10, 4, 5] per = 20 result = trimmean(arr, per) print(result) # Should print 7.0 ``` In this example, after sorting: [4, 5, 6, 7, 8, 9, 10], trimming 20% means removing the lowest 10% (1 element) and the highest 10% (1 element), leaving [5, 6, 7, 8, 9]. The mean of these numbers is 7.0. Implement the function `trimmean(arr, per)` to compute this correctly. Be sure to handle edge cases such as percentages resulting in zero removals and minimal input lists.
answer:from typing import List def trimmean(arr: List[float], per: float) -> float: Calculate the mean of the list after removing a certain percentage of the largest and smallest values. Args: arr (List[float]): a list of floats. per (float): a float percentage between 0 and 100. Returns: float: the trimmed mean of the list. n = len(arr) trim_count = int(n * per / 100 // 2) sorted_arr = sorted(arr) trimmed_arr = sorted_arr[trim_count:n-trim_count] return sum(trimmed_arr) / len(trimmed_arr)