GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Python/backtracking/word_break.py at master · bogdaniel/Python Expand file tree/ Copy pathword_break.pyMore file actions 74 lines (54 loc) · 2.1 KB / Copy pathword_break.pyFile metadata and controls74 lines (54 loc) · 2.1 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 """ Word Break Problem is a well-known problem in computer science. Given a string and a dictionary of words, the task is to determine if the string can be segmented into a sequence of one or more dictionary words. Wikipedia: https://en.wikipedia.org/wiki/Word_break_problem """ def backtrack(input_string: str, word_dict: set[str], start: int) -> bool: """ Helper function that uses backtracking to determine if a valid word segmentation is possible starting from index 'start'. Parameters: input_string (str): The input string to be segmented. word_dict (set[str]): A set of valid dictionary words. start (int): The starting index of the substring to be checked. Returns: bool: True if a valid segmentation is possible, otherwise False. Example: >>> backtrack("leetcode", {"leet", "code"}, 0) True >>> backtrack("applepenapple", {"apple", "pen"}, 0) True >>> backtrack("catsandog", {"cats", "dog", "sand", "and", "cat"}, 0) False """ # Base case: if the starting index has reached the end of the string if start == len(input_string): return True # Try every possible substring from 'start' to 'end' for end in range(start + 1, len(input_string) + 1): if input_string[start:end] in word_dict and backtrack( input_string, word_dict, end ): return True return False def word_break(input_string: str, word_dict: set[str]) -> bool: """ Determines if the input string can be segmented into a sequence of valid dictionary words using backtracking. Parameters: input_string (str): The input string to segment. word_dict (set[str]): The set of valid words. Returns: bool: True if the string can be segmented into valid words, otherwise False. Example: >>> word_break("leetcode", {"leet", "code"}) True >>> word_break("applepenapple", {"apple", "pen"}) True >>> word_break("catsandog", {"cats", "dog", "sand", "and", "cat"}) False >>> word_break("applepenapple", {}) False """ return backtrack(input_string, word_dict, 0) |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |