[LeetCode] 3042. Count Prefix and Suffix Pairs I

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

leetcode - Count Prefix and Suffix Pairs I

문제 유형: 문자열 처리

문제 난이도: Easy

 

문제

You are given a 0-indexed string array words.

Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:

• isPrefixAndSuffix(str1, str2) returns true if str1 is both a 
  prefix
   and a 
  suffix
   of str2, and false otherwise.

For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.

Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.

 

isPrefixAndSuffix(str1, str2)는 str1이 str2의 prefix이면서 suffix인경우 true를 반환한다.

isPrefixAndSuffix(words[i], words[j])를 만족하는 쌍 (i, j)의 개수를 구하시오.

 

풀이

그래도 구현해주면 된다.

한 번의 순회로 prefix와 suffix를 동시에 확인할 수 있다.(아래 코드 참조)

 

코드

C++

class Solution {
public:
    bool isPrefixAndSuffix(const string& str1, const string& str2) {
        int a = str1.size();
        int b = str2.size();
        if(str1.size() > str2.size()) return false;
        for(int i = 0; i < str1.size(); ++i) {
            if(str1[i] != str2[i] || str1[a-i-1] != str2[b-i-1]) return false;
        }
        return true;
    }
    int countPrefixSuffixPairs(vector<string>& words) {
        int ans = 0;
        int n = words.size();
        for(int i = 0; i < n; ++i) {
            for(int j = i+1; j < n; ++j) {
                if(isPrefixAndSuffix(words[i], words[j])) ans++;
            }
        }
        return ans;
    }
};