Understand Count Prefix and Suffix Pairs I Problem

Problem Name: Count Prefix and Suffix Pairs I
Problem Description:

Problem: Count Prefix and Suffix Pairs

You are given an array of strings called words. Your task is to count the number of pairs (i, j) (where i < j) such that a string words[i] is both a prefix and a suffix of another string words[j].

Key Definitions:

  • Prefix : A string str1 is a prefix of str2 if str2 starts with str1. Example: "ab" is a prefix of "abc", but not of "cab".
  • Suffix: A string str1 is a suffix of str2 if str2 ends with str1.
    Example: "bc" is a suffix of "abc", but not of "bca".
  • Prefix and Suffix: A string str1 is both a prefix and suffix of str2 if: - str2 starts with str1, and - str2 ends with str1.

Examples:

Example 1:

Input: words = ["a", "aba", "ababa", "aa"]
Output: 4

Explanation:
The valid pairs (i, j) are:

  1. (0, 1) because "a" is both a prefix and suffix of "aba".
  2. (0, 2) because "a" is both a prefix and suffix of "ababa".
  3. (0, 3) because "a" is both a prefix and suffix of "aa".
  4. (1, 2) because "aba" is both a prefix and suffix of "ababa".

Example 2:

Input: words = ["pa", "papa", "ma", "mama"]
Output: 2

Explanation:
The valid pairs (i, j) are:

  1. (0, 1) because "pa" is both a prefix and suffix of "papa".
  2. (2, 3) because "ma" is both a prefix and suffix of "mama".

Example 3:

Input: words = ["abab", "ab"]
Output: 0

Explanation:
No valid pairs exist because none of the strings in words satisfy the condition of being both a prefix and suffix.

Constraints:

  • 1 <= words.length <= 50
  • 1 <= words[i].length <= 10
  • words[i] contains only lowercase English letters.

Goal:

Return the total number of valid (i, j) pairs where i < j and words[i] is both a prefix and a suffix of words[j].

Category:
  • Leetcode Problem of the Day
  • Tries
  • Arrays
  • Strings
  • Heaps & Hashing
Programming Language:
  • Java
Reference Link:

https://leetcode.com/problems/count-prefix-and-suffix-pairs-i/description/

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
Main Function is not defined.
Helper Function:
INPUT: words = ["a", "aba", "ababa", "aa"]
OUTPUT: 4
public static int countPrefixSuffixPairs(String[] words) {
int count = 0;
int n = words.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
boolean condition = isPrefixAndSuffix(words[i], words[j]);
if(condition) {
count++; 
}//If End
}//Loop End
}//Loop End
return count;
}//function end
Utility Functions and Global variables:
public static boolean isPrefixAndSuffix(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
if (len1 > len2){
return false;
}
boolean isPrefix = str2.startsWith(str1);
boolean isSuffix = str2.endsWith(str1);
return isPrefix && isSuffix;
}function end
Privacy Policy | About