question:# Question: Pattern Matching Bijection You are given a pattern string and a text string containing multiple words separated by spaces. Your task is to implement a function `word_pattern(pattern: str, text: str) -> bool` that determines if the text string follows the same pattern as the pattern string. Here, "following the same pattern" means that each character in the pattern string should map to a unique word in the text string, forming a bijective relationship. Input - A string `pattern` containing only lowercase alphabetical characters. - A string `text` containing words separated by single spaces. Output - A boolean value indicating whether the text follows the pattern (True) or not (False). Constraints - The `pattern` string could have a length up to 100. - The `text` string could have a maximum of 100 words. - Each word in the `text` string has between 1 and 20 lowercase alphabetical characters. Performance Requirements - The algorithm should operate in linear time relative to the length of the input strings and use space linearly proportional to the number of unique pattern characters and words. Examples ```python assert word_pattern("abba", "dog cat cat dog") == True assert word_pattern("abba", "dog cat cat fish") == False assert word_pattern("aaaa", "dog cat cat dog") == False assert word_pattern("abba", "dog dog dog dog") == False ``` Explanation 1. In the first example, pattern "abba" maps to text "dog cat cat dog" since 'a' -> 'dog', 'b' -> 'cat'. 2. In the second example, pattern "abba" cannot map to text "dog cat cat fish" due to the mismatch at the last word. 3. In the third example, pattern "aaaa" cannot map to "dog cat cat dog" since 'a' would need to map to different words. 4. In the fourth example, pattern "abba" cannot map to "dog dog dog dog" since multiple characters cannot map to the same word. Implement the `word_pattern` function considering the above requirements and constraints.

question:# Question: Subset Generation using Backtracking and Iterative Approach Given a set of distinct integers, `nums`, you need to implement two functions that return all possible subsets. 1. `subsets_backtrack(nums: List[int]) -> List[List[int]]`: Using a backtracking approach. 2. `subsets_iterative(nums: List[int]) -> List[List[int]]`: Using an iterative approach. **Input:** - `nums`: A list of distinct integers, up to 10 elements. **Output:** - Return a list of lists where each list represents a possible subset of the given integers. **Constraints:** - Distinct integers only, no duplicate subsets. - The result should contain the empty subset and all other combinations of elements. - Elements within subsets can be in any order, but the overall output should not have duplicate subsets. **Performance Requirements:** - Both implementations should produce results within the constraints and perform efficiently for the input size provided. # Examples: Example 1: ``` Input: nums = [1,2,3] Output: [ [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] ] ``` Example 2: ``` Input: nums = [0] Output: [ [], [0] ] ``` # Function Signatures: ```python from typing import List def subsets_backtrack(nums: List[int]) -> List[List[int]]: # Implement the backtracking approach here pass def subsets_iterative(nums: List[int]) -> List[List[int]]: # Implement the iterative approach here pass ``` Requirements 1. Ensure that your solution does not produce duplicate subsets. 2. Verify that both methods produce the correct output as shown in the examples. 3. Explain why you chose your specific implementation details for each method.

question:# Problem Description You are tasked with implementing a function that simulates the addition of one to a non-negative integer represented by a list of digits. The digits are stored in big-endian order, meaning the most significant digit is at the head of the list. Your function should account for the necessary carry management. # Input * A list of non-negative integers where each integer represents a digit. Assume no leading zeros except if the number is zero itself. # Output * A list of non-negative integers representing the new number after adding one. # Constraints 1. The length of the digits list would be between 1 and 10,000. 2. Each element in the input list will be a single digit between 0 and 9. # Performance Requirements * The algorithm should run in O(n) time complexity, where n is the number of digits. # Function Signature ```python def increment_number(digits: List[int]) -> List[int]: ``` # Example ```python # Example 1 input_digits = [1, 2, 3] output_digits = [1, 2, 4] # Example 2 input_digits = [9, 9, 9] output_digits = [1, 0, 0, 0] # Example 3 input_digits = [0] output_digits = [1] ``` # Explanation 1. In the first example, `1, 2, 3` represents 123. Adding one results in 124. 2. In the second example, adding one to `999` results in `1000`, demonstrating the carry-over through all digits. 3. The third example handles a minimal input case where a single digit is incremented. Implement the above function: ```python from typing import List def increment_number(digits: List[int]) -> List[int]: n = len(digits) for i in range(n-1, -1, -1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 return [1] + digits ```

question:You are provided with integers, and your task is to determine if each integer is a perfect square. If it is, compute and return the next perfect square. Otherwise, return -1. Function Signature ```python def find_next_square(sq: int) -> int: ``` Input * `sq` (int): A non-negative integer you need to evaluate. Output * (int): The next perfect square if `sq` is a perfect square, otherwise -1. Constraints * The provided integer `sq` will be in the range of a 32-bit signed integer. # Performance Requirements * The solution should run in constant time O(1) and use constant space O(1). # Examples ```python assert find_next_square(121) == 144 # 121 is a perfect square (11^2), next is 12^2 = 144 assert find_next_square(625) == 676 # 625 is a perfect square (25^2), next is 26^2 = 676 assert find_next_square(114) == -1 # 114 is not a perfect square assert find_next_square(-4) == -1 # Negative numbers cannot be perfect squares assert find_next_square(0) == 1 # 0 is a perfect square (0^2), next is 1^2 = 1 ``` Implement the function `find_next_square` adhering to the above requirements.