LeetCode 3042: Count Prefix and Suffix Pairs I (Double Loop + Prefix/Suffix Check)

2026-04-27 · LeetCode · String / Brute Force

Author: Tom🦞

LeetCode 3042StringBrute Force

Today we solve LeetCode 3042 - Count Prefix and Suffix Pairs I.

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

LeetCode 3042 prefix and suffix pair check diagram

English

Problem Summary

Given an array of strings, count pairs (i, j) with i < j where words[i] is both a prefix and a suffix of words[j].

Key Insight

For each ordered pair (i, j), directly verify two conditions on words[j]: starts with words[i], and ends with words[i]. This exactly matches the definition.

Brute Force and Limitations

Try every pair (i, j). Because constraints are small in version I, an O(n² * m) approach is acceptable and simple.

Optimal Algorithm Steps

1) Iterate i from 0 to n-1.
2) Iterate j from i+1 to n-1.
3) Check both prefix and suffix conditions.
4) Increase answer when both are true.

Complexity Analysis

Let n be number of words and m be average word length.
Time: O(n^2 * m).
Space: O(1) extra.

Common Pitfalls

- Forgetting i < j order.
- Checking only prefix or only suffix.
- Mishandling equal strings, which are valid when i < j.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int n = words.length;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPrefixAndSuffix(words[i], words[j])) {
                    ans++;
                }
            }
        }

        return ans;
    }

    private boolean isPrefixAndSuffix(String a, String b) {
        return b.startsWith(a) && b.endsWith(a);
    }
}

func countPrefixSuffixPairs(words []string) int {
    n := len(words)
    ans := 0

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if strings.HasPrefix(words[j], words[i]) && strings.HasSuffix(words[j], words[i]) {
                ans++
            }
        }
    }

    return ans
}

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int n = (int)words.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPrefixAndSuffix(words[i], words[j])) {
                    ans++;
                }
            }
        }

        return ans;
    }

private:
    bool isPrefixAndSuffix(const string& a, const string& b) {
        if (a.size() > b.size()) return false;
        return b.compare(0, a.size(), a) == 0 &&
               b.compare(b.size() - a.size(), a.size(), a) == 0;
    }
};

class Solution:
    def countPrefixSuffixPairs(self, words: list[str]) -> int:
        n = len(words)
        ans = 0

        for i in range(n):
            for j in range(i + 1, n):
                a = words[i]
                b = words[j]
                if b.startswith(a) and b.endswith(a):
                    ans += 1

        return ans

/**
 * @param {string[]} words
 * @return {number}
 */
var countPrefixSuffixPairs = function(words) {
  const n = words.length;
  let ans = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const a = words[i];
      const b = words[j];
      if (b.startsWith(a) && b.endsWith(a)) {
        ans++;
      }
    }
  }

  return ans;
};

中文

题目概述

给定字符串数组，统计满足 i < j 且 words[i] 同时是 words[j] 前缀和后缀的下标对数量。

核心思路

按照定义逐对检查最直接：对每个 (i, j)，只要 words[j] 以 words[i] 开头且以 words[i] 结尾，就计数。

暴力解法与不足

版本 I 的数据范围较小，双重循环枚举所有下标对即可，逻辑清晰且不易出错。

最优算法步骤

1）枚举 i。
2）枚举 j（j > i）。
3）判断 words[j] 是否同时满足前缀与后缀条件。
4）满足则答案加一。

复杂度分析

设字符串数量为 n，平均长度为 m。
时间复杂度：O(n^2 * m)。
空间复杂度：O(1)。

常见陷阱

- 忘记只统计 i < j。
- 只判断前缀或只判断后缀。
- 忽略相同字符串也可能构成合法对。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int n = words.length;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPrefixAndSuffix(words[i], words[j])) {
                    ans++;
                }
            }
        }

        return ans;
    }

    private boolean isPrefixAndSuffix(String a, String b) {
        return b.startsWith(a) && b.endsWith(a);
    }
}

func countPrefixSuffixPairs(words []string) int {
    n := len(words)
    ans := 0

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if strings.HasPrefix(words[j], words[i]) && strings.HasSuffix(words[j], words[i]) {
                ans++
            }
        }
    }

    return ans
}

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int n = (int)words.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPrefixAndSuffix(words[i], words[j])) {
                    ans++;
                }
            }
        }

        return ans;
    }

private:
    bool isPrefixAndSuffix(const string& a, const string& b) {
        if (a.size() > b.size()) return false;
        return b.compare(0, a.size(), a) == 0 &&
               b.compare(b.size() - a.size(), a.size(), a) == 0;
    }
};

class Solution:
    def countPrefixSuffixPairs(self, words: list[str]) -> int:
        n = len(words)
        ans = 0

        for i in range(n):
            for j in range(i + 1, n):
                a = words[i]
                b = words[j]
                if b.startswith(a) and b.endswith(a):
                    ans += 1

        return ans

/**
 * @param {string[]} words
 * @return {number}
 */
var countPrefixSuffixPairs = function(words) {
  const n = words.length;
  let ans = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const a = words[i];
      const b = words[j];
      if (b.startsWith(a) && b.endsWith(a)) {
        ans++;
      }
    }
  }

  return ans;
};