# Posts tagged as “prefix”

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.


Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.


Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.


Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4


Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1


Constraints:

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

## Solution 1: Brute Force

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

## C++

Given an array of integers arr.

We want to select three indices ij and k where (0 <= i < j <= k < arr.length).

Let’s define a and b as follows:

• a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
• b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (ij and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)


Example 2:

Input: arr = [1,1,1,1,1]
Output: 10


Example 3:

Input: arr = [2,3]
Output: 0


Example 4:

Input: arr = [1,3,5,7,9]
Output: 3


Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8


Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 10^8

## Solution 1: Brute Force (TLE)

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

## Solution 2: Prefix XORs

Let xors[i] = arr[0] ^ arr[1] ^ … ^ arr[i-1]
arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] = (arr[0] ^ … ^ arr[j – 1]) ^ (arr[0] ^ … ^ arr[i-1]) = xors[j] ^ xors[i]

We then can compute a and b in O(1) time.

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

## Solution 3: Prefix XORs II

a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
a == b => a ^ b == 0
XORs(i ~ k) == 0
XORS(0 ~ k) ^ XORs(0 ~ i – 1) = 0

Problem => find all pairs of (i – 1, k) such that xors[k+1] == xors[i]
For each pair (i – 1, k), there are k – i positions we can insert j.

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

## Solution 3: HashTable

Similar to target sum, use a hashtable to store the frequency of each prefix xors.

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

## C++

KMP Algorithm, KMP 字符串搜索算法

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

## Applications

LeetCode 28. strStr()

## C++

LeetCode 459. Repeated Substring Pattern

## C++

1392. Longest Happy Prefix

## C++

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 (ijk) 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)

## 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++

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
[[],[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.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.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)