Posts tagged as “prefix”

KMP Algorithm SP19

By zxi on March 31, 2020

KMP Algorithm, KMP 字符串搜索算法

Time complexity: O(m+n)
Space complexity: O(m)

Implementation

C++

#include <iostream>

#include <vector>

using namespace std;

// Author: Huahua

namespace KMP {

vector<int> Build(const string& p) {

const int m = p.length();

vector<int> nxt{0, 0};

for (int i = 1, j = 0; i < m; ++i) {

while (j > 0 && p[i] != p[j])

j = nxt[j];

if (p[i] == p[j])

++j;

nxt.push_back(j);

}

return nxt;

}

vector<int> Match(const string& s, const string& p) {

vector<int> nxt(Build(p));

vector<int> ans;

const int n = s.length();

const int m = p.length();

for (int i = 0, j = 0; i < n; ++i) {

while (j > 0 && s[i] != p[j])

j = nxt[j];

if (s[i] == p[j])

++j;

if (j == m) {

ans.push_back(i - m + 1);

j = nxt[j];

}

return ans;

}

}; // namespace KMP

void CheckEQ(const vector<int>& actual, const vector<int>& expected) {

if (actual != expected) {

std::cout << "expected:";

for (int v : expected)

std::cout << " " << v;

std::cout << " actual:";

for (int v : actual)

std::cout << " " << v;

std::cout << std::endl;

} else {

std::cout << "PASS" << std::endl;

}

int main(int argc, char** argv) {

CheckEQ(KMP::Build("ABCDABD"), {0, 0, 0, 0, 0, 1, 2, 0});

CheckEQ(KMP::Build("AB"), {0, 0, 0});

CheckEQ(KMP::Build("A"), {0, 0});

CheckEQ(KMP::Build("AA"), {0, 0, 1});

CheckEQ(KMP::Build("AAA"), {0, 0, 1, 2});

CheckEQ(KMP::Build("AABA"), {0, 0, 1, 0, 1});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), {15});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "AB"), {0, 4, 8, 11, 15, 19});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "B"), {1, 5, 9, 12, 16, 20});

CheckEQ(KMP::Match("AAAAA", "A"), {0, 1, 2, 3, 4});

CheckEQ(KMP::Match("AAAAA", "AA"), {0, 1, 2, 3});

CheckEQ(KMP::Match("AAAAA", "AAA"), {0, 1, 2});

CheckEQ(KMP::Match("ABC", "ABC"), {0});

return 0;

}

Python3

#!/usr/bin/env python3

from typing import List

# Author: Huahua

def Build(p: str) -> List[int]:

m = len(p)

nxt = [0, 0]

j = 0

for i in range(1, m):

while j > 0 and p[i] != p[j]:

j = nxt[j]

if p[i] == p[j]:

j += 1

nxt.append(j)

return nxt

def Match(s: str, p: str) -> List[int]:

n, m = len(s), len(p)

nxt = Build(p)

ans = []

j = 0

for i in range(n):

while j > 0 and s[i] != p[j]:

j = nxt[j]

if s[i] == p[j]:

j += 1

if j == m:

ans.append(i - m + 1)

j = nxt[j]

return ans

def CheckEQ(actual, expected):

if actual != expected:

print('actual: %s, expected: %s' % (actual, expected))

else:

print('Pass')

if __name__ == "__main__":

CheckEQ(Build("ABCDABD"), [0, 0, 0, 0, 0, 1, 2, 0])

CheckEQ(Build("AB"), [0, 0, 0])

CheckEQ(Build("A"), [0, 0])

CheckEQ(Build("AA"), [0, 0, 1])

CheckEQ(Build("AAAA"), [0, 0, 1, 2, 3])

CheckEQ(Build("AABA"), [0, 0, 1, 0, 1])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), [15])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "AB"), [0, 4, 8, 11, 15, 19])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "B"), [1, 5, 9, 12, 16, 20])

CheckEQ(Match("AAAAA", "A"), [0, 1, 2, 3, 4])

CheckEQ(Match("AAAAA", "AA"), [0, 1, 2, 3])

CheckEQ(Match("AAAAA", "AAAA"), [0, 1])

CheckEQ(Match("AAAAA", "AAAAA"), [0])

CheckEQ(Match("AABAABA", "AABA"), [0, 3])

Applications

LeetCode 28. strStr()

C++

// Author: Huahua

class Solution {

public:

int strStr(string haystack, string needle) {

if (needle.empty()) return 0;

auto matches = KMP::Match(haystack, needle);

return matches.empty() ? -1 : matches[0];

}

};

LeetCode 459. Repeated Substring Pattern

C++

// Author: Huahua

class Solution {

public:

bool repeatedSubstringPattern(string str) {

const int n = str.length();

auto nxt = KMP::Build(str);

return nxt[n] && nxt[n] % (n - nxt[n]) == 0;

}

};

1392. Longest Happy Prefix

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(const string& s) {

return s.substr(0, KMP::Build(s).back());

}

};

花花酱 LeetCode 1395. Count Number of Teams

By zxi on March 28, 2020

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

Solution 1: Brute Force

Time complexity: O(n^3)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

for (int k = j + 1; k < n; ++k)

if (rating[i] < rating[j] && rating[j] < rating[k]

|| rating[i] > rating[j] && rating[j] > rating[k])

++ans;

return ans;

}

};

Solution 2: Math

For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many soldiers his right side has larger ratings as right[j]

ans = sum(left[j] * right[j] + (j – left[j]) * (n – j – 1 * right[j])

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

for (int j = 0; j < n; ++j) {

int l = 0;

int r = 0;

for (int i = 0; i < j; ++i)

if (rating[i] < rating[j]) ++l;

for (int k = j + 1; k < n; ++k)

if (rating[j] < rating[k]) ++r;

ans += (l * r) + (j - l) * (n - j - 1 - r);

}

return ans;

}

};

花花酱 LeetCode 1352. Product of the Last K Numbers

By zxi on February 16, 2020

Implement the class ProductOfNumbers that supports two methods:

1. add(int num)

Adds the number num to the back of the current list of numbers.

2. getProduct(int k)

Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:

Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output: [null,null,null,null,null,null,20,40,0,null,32]
Explanation:
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3] 
productOfNumbers.add(0);        // [3,0] 
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20.
The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40 
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32

Constraints:

There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

Solution: Prefix product

Use p[i] to store the prod of a1*a2*…ai
p[i] = ai*p[i-1]
If ai is 0, reset p = [1].
Compare k with the len(p), if k is greater than len(p) which means there is 0 recently, return 0.
otherwise return p[n] / p[n – k – 1]

Time complexity: Add: O(1), getProduct: O(1)
Space complexity: O(n)

C++

// Author: Huahua

class ProductOfNumbers {

public:

ProductOfNumbers(): p_(1, 1) { }

void add(int num) {

if (num == 0) {

p_.clear();

p_.push_back(1);

} else {

p_.push_back(p_.back() * num);

}

int getProduct(int k) {

if (k >= p_.size()) return 0;

// a_1*a_2*...*a_n / a_1*a_2*...*a_n-k-1.

return p_.back() / p_[p_.size() - k - 1];

}

private:

vector<int> p_;

};

花花酱 LeetCode 1268. Search Suggestions System

By zxi on November 24, 2019

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
All characters of products[i] are lower-case English letters.
1 <= searchWord.length <= 1000
All characters of searchWord are lower-case English letters.

Solution 1: Binary Search

Sort the input array and do two binary searches.
One for prefix of the search word as lower bound, another for prefix + ‘~’ as upper bound.
‘~’ > ‘z’

Time complexity: O(nlogn + l * logn)
Space complexity: O(1)

C++

// Author: Huahua, 36ms, 35MB

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

vector<vector<string>> ans;

std::sort(begin(products), end(products));

string key;

for (char c : searchWord) {

key += c;

auto l = lower_bound(begin(products), end(products), key);

auto r = upper_bound(begin(products), end(products), key += '~');

if (l == r) break; // early return

key.pop_back();

ans.emplace_back(l, min(l + 3, r));

}

while (ans.size() != searchWord.length()) ans.push_back({});

return ans;

}

};

Solution 2: Trie

Initialization: Sum(len(products[i]))
Query: O(len(searchWord))

C++

// Author: Huahua, 148 ms, 98.8 MB

struct Trie {

Trie(): nodes(26) {}

~Trie() {

for (auto* node : nodes)

delete node;

}

vector<Trie*> nodes;

vector<const string*> words;

static void addWord(Trie* root, const string& word) {

for (char c : word) {

if (root->nodes[c - 'a'] == nullptr) root->nodes[c - 'a'] = new Trie();

root = root->nodes[c - 'a'];

if (root->words.size() < 3)

root->words.push_back(&word);

}

static vector<vector<string>> getWords(Trie* root, const string& prefix) {

vector<vector<string>> ans(prefix.size());

for (int i = 0; i < prefix.size(); ++i) {

char c = prefix[i];

root = root->nodes[c - 'a'];

if (root == nullptr) break;

for (auto* word : root->words)

ans[i].push_back(*word);

}

return ans;

}

};

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

std::sort(begin(products), end(products));

Trie root;

for (const auto& product : products)

Trie::addWord(&root, product);

return Trie::getWords(&root, searchWord);

}

};

花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

for (int i = 0; i < 26; ++i)

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

if (!ans.empty()) ans += ' ';

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};