3839. Number of Prefix Connected Groups Medium

1/**
2 * [3839] Number of Prefix Connected Groups
3 *
4 * You are given an array of strings words and an integer k.
5 * Two words a and b at distinct indices are <span data-keyword="string-prefix">prefix</span>-connected if a[0..k-1] == b[0..k-1].
6 * A connected group is a set of words such that each pair of words is prefix-connected.
7 * Return the number of connected groups that contain at least two words, formed from the given words.
8 * Note:
9 * 
10 * 	Words with length less than k cannot join any group and are ignored.
11 * 	Duplicate strings are treated as separate words.
12 * 
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">words = ["apple","apply","banana","bandit"], k = 2</span>
17 * Output: <span class="example-io">2</span>
18 * Explanation:
19 * Words sharing the same first k = 2 letters are grouped together:
20 * 
21 * 	words[0] = "apple" and words[1] = "apply" share prefix "ap".
22 * 	words[2] = "banana" and words[3] = "bandit" share prefix "ba".
23 * 
24 * Thus, there are 2 connected groups, each containing at least two words.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">words = ["car","cat","cartoon"], k = 3</span>
29 * Output: <span class="example-io">1</span>
30 * Explanation:
31 * Words are evaluated for a prefix of length k = 3:
32 * 
33 * 	words[0] = "car" and words[2] = "cartoon" share prefix "car".
34 * 	words[1] = "cat" does not share a 3-length prefix with any other word.
35 * 
36 * Thus, there is 1 connected group.
37 * </div>
38 * <strong class="example">Example 3:
39 * <div class="example-block">
40 * Input: <span class="example-io">words = </span>["bat","dog","dog","doggy","bat"]<span class="example-io">, k = 3</span>
41 * Output: <span class="example-io">2</span>
42 * Explanation:
43 * Words are evaluated for a prefix of length k = 3:
44 * 
45 * 	words[0] = "bat" and words[4] = "bat" form a group.
46 * 	words[1] = "dog", words[2] = "dog" and words[3] = "doggy" share prefix "dog".
47 * 
48 * Thus, there are 2 connected groups, each containing at least two words.
49 * </div>
50 *  
51 * Constraints:
52 * 
53 * 	1 <= words.length <= 5000
54 * 	1 <= words[i].length <= 100
55 * 	1 <= k <= 100
56 * 	All strings in words consist of lowercase English letters.
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/number-of-prefix-connected-groups/
62// discuss: https://leetcode.com/problems/number-of-prefix-connected-groups/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn prefix_connected(words: Vec<String>, k: i32) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_3839() {
80    }
81}
82