## Problem Split a string of decimal digits into exactly `k` segments. Each segment must represent an integer from 0 through 255 and may not contain a leading zero unless the segment is exactly `"0"`. Return every valid address by joining its segments with dots in lexicographic order. ### Function Contract Implement `restore_addresses(digits, k) -> list[str]`. ### Constraints - `1 <= len(digits) <= 30` and `1 <= k <= 10`. - The input contains only characters `0` through `9`. - Every segment has length between 1 and 3. - The returned list contains no duplicates. ### Examples - `digits = "25525511135"`, `k = 4` returns `["255.255.11.135", "255.255.111.35"]`. - `digits = "0000"`, `k = 4` returns `["0.0.0.0"]`. ```hint Prune by remaining length If `r` segments remain, the remaining digits must number between `r` and `3r`. ``` ```hint Reject a zero prefix immediately After choosing a segment that begins with zero, do not try a longer version of that segment. ``` ### Edge Cases - A segment value of exactly 255 is valid; 256 is not. - The requested number of segments may make every split impossible. - For `k` other than four, the same segment rules still apply.