Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Suffix Count

Suffix Count

Solve an easy problem for finding the count of words with a suffix.

We'll cover the following...

Problem statement

A suffix is a letter or a contiguous group of letters present at the end of a string. Given an array of strings words and a string suff, return the number of strings in words that contain suff as a suffix.

Example 1

Sample Input

words: ["paid", "said", "maid", "raid", "apple", "maple", "staple"]
suff: "id"

Sample output

4

Explanation

The four strings, "paid", "said", "maid" and "raid" contain "id" as a suffix.

Example 2

Sample Input

words: ["paid", "said", "maid", "raid", "apple", "maple", "staple"]
suff: "ple"

Sample output

3

Explanation

The three strings, "apple", "maple" and "staple", contain "ple" as a suffix.

Try it yourself

Try to solve the problem yourself before reading the solution.

#include <iostream>

#include <vector>

using namespace std;



int suffixCount(vector<string>& words, string suff) {

  // your code goes here

  return -1;

}
Solve suffix count in C++

Intuition

The problem can be rephrased as counting the number of words in a list with a given suffix. A naive solution would be to traverse through all the words in the given list and check if the word has suff as the suffix.

// returns the count of words in the list, which have suff as a suffix
int suffixCount(words, suff) 
{
    count = 0
    for every word in words list
        //check if suff is a suffix of word
        if isSuffix(suff, word) is true
            count+1
    return count
}
// checks if suff is a suffix of word 
boolean isSuffix(suff, word)
{
    for char at index i the reversed (suff) and in the reversed (word)
        if character at index in suff, equals to the character at index in word
            continue
        else 
            break 
        
    if the value of index equals the length of suff
        return true
}
Pseudocode for brute-force approach

To check if suff is a suffix of a word, we traverse and compare all characters of both the word and suff simultaneously. This operation adds a time complexity of O(W)O(W), where WW is the maximum length of the suff. This comparison operation is performed for all the N ...

Access this course and 1400+ top-rated courses and projects.