leetcode/strings/1408-string-matching-in-an-array.go at main · shahzodshafizod/leetcode · GitHub

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package strings

import "sort"

// https://leetcode.com/problems/string-matching-in-an-array/

// Approach: KMP (Knutt-Morris-Pritt)
// Time: O(nnm), n=len(words), m=len(words[i])
// Space: O(m)
func stringMatching(words []string) []string {
	getLPS := func(word string) []int {
		m := len(word)
		lps := make([]int, m)

		p, s := 0, 1
		for s < m {
			if word[s] == word[p] {
				p++
				lps[s] = p
				s++
			} else if p == 0 {
				s++
			} else {
				p = lps[p-1]
			}
		}

		return lps
	}

	sort.Slice(words, func(i int, j int) bool { return len(words[i]) < len(words[j]) })
	n := len(words)
	check := func(curr string, start int) bool {
		m := len(curr)
		lps := getLPS(curr)

		var cid, nid, nlen int

		for idx := start; idx < n; idx++ {
			next := words[idx]

			nlen = len(next)
			if nlen == m {
				continue
			}

			cid, nid = 0, 0
			for cid < m && nid < nlen {
				if curr[cid] == next[nid] {
					cid++
					nid++
				} else if cid == 0 {
					nid++
				} else {
					cid = lps[cid-1]
				}
			}

			if cid == m {
				return true
			}
		}

		return false
	}
	result := make([]string, 0)

	for idx, word := range words {
		if check(word, idx+1) {
			result = append(result, word)
		}
	}

	return result
}

// // Approach: Trie
// // Time: O(nmm), n=len(words), m=len(words[i])
// // Space: O(nm)
// func stringMatching(words []string) []string {
// 	type TrieNode struct {
// 		count int
// 		children map[rune]*TrieNode
// 	}
// 	var NewTrieNode = func() *TrieNode {
// 		return &TrieNode{children: make(map[rune]*TrieNode)}
// 	}
// 	var root = NewTrieNode()
// 	var n = len(words)
// 	var nodes = make([]*TrieNode, n)
// 	var m int
// 	for idx, word := range words {
// 		m = len(word)
// 		for j := 0; j < m; j++ {
// 			curr := root
// 			for _, c := range word[j:] {
// 				if curr.children[c] == nil {
// 					curr.children[c] = NewTrieNode()
// 				}
// 				curr = curr.children[c]
// 				curr.count++
// 			}
// 			if nodes[idx] == nil {
// 				nodes[idx] = curr
// 			}
// 		}
// 	}
// 	var result = make([]string, 0)
// 	for idx := range nodes {
// 		if nodes[idx].count >= 2 {
// 			result = append(result, words[idx])
// 		}
// 	}
// 	return result
// }