Question
Formatted question description: https://leetcode.ca/all/1698.html
1698. Number of Distinct Substrings in a String
Given a string s, return the number of distinct substrings of s.
A substring of a string is obtained by deleting any number of characters (possibly zero)
from the front of the string and any number (possibly zero) from the back of the string.
Example 1:
Input: s = "aabbaba"
Output: 21
Explanation: The set of distinct strings is ["a","b","aa","bb","ab","ba","aab","abb","bba","aba","aabb","abba","bbab","baba","aabba","abbab","bbaba","aabbab","abbaba","aabbaba"]
Example 2:
Input: s = "abcdefg"
Output: 28
Constraints:
1 <= s.length <= 500
s consists of lowercase English letters.
Follow up: Can you solve this problem in O(n) time complexity?
Algorithm
Use a Trie, and every time a new Trie node created, meaning a new substring.
If O(n) time complexity, then we need some extra space to store for de-dup check, like a Set.
Code
Java
public class Number_of_Distinct_Substrings_in_a_String {
class Solution_oN {
int result = 0;
Node trie[] = new Node[26];
class Node {
Node children[] = new Node[26];
int count = 0;
}
public int countDistinct(String s) {
for (int i = 0; i < s.length(); i++) {
insert(trie, s, i);
}
for (int i = 0; i < s.length(); i++) {
find(trie, s, i);
}
return result;
}
public void insert(Node trie[], String s, int index) {
if (index >= s.length()) {
return;
}
int i = s.charAt(index) - 'a';
if (trie[i] == null) {
trie[i] = new Node();
}
insert(trie[i].children, s, index + 1);
}
public void find(Node trie[], String s, int index) {
if (index >= s.length()) {
return;
}
int i = s.charAt(index) - 'a';
trie[i].count++;
if (trie[i].count == 1) {
this.result++;
}
find(trie[i].children, s, index + 1);
}
}
public class Solution {
class Trie {
Trie[] children = new Trie[26];
}
public int countDistinct(String s) {
Trie root = new Trie();
Trie current;
int count = 0;
for (int i = 0; i < s.length(); i++) {
current = root;
for (int j = i; j < s.length(); j++) {
if (current.children[s.charAt(j) - 'a'] == null) {
current.children[s.charAt(j) - 'a'] = new Trie();
count++;
}
current = current.children[s.charAt(j) - 'a'];
}
}
return count;
}
}
public class Solution_oN2 {
Set<String> set = new HashSet<>();
public int countDistinct(String s) {
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
set.add(s.substring(i, j + 1));
}
}
return set.size();
}
}
}