FoxAndWord | Topcoder Archive

Problem Statement

One day, Fox Ciel looked at the words "tokyo" and "kyoto" and noticed an unusual property: We can split "tokyo" into "to"+"kyo", and then swap those two parts to obtain "kyo"+"to" = "kyoto".

Formally, let S and T be two different strings. We call the pair (S,T) interesting if there are two non-empty strings A and B such that S = A+B and T = B+A. For example, according to this definition, if S="tokyo" and T="kyoto", then the pair (S,T) is interesting, because we can find A="to" and B="kyo".

You are given a String[] words. Return the number of interesting pairs we can find among the elements of words. Only count each pair once. E.g., ("tokyo","kyoto") and ("kyoto","tokyo") is the same interesting pair.

Definition

Class:: FoxAndWord
Method:: howManyPairs
Parameters:: String[]
Returns:: int
Method signature:: int howManyPairs(String[] words)
(be sure your method is public)

Constraints

words will contain between 2 and 50 elements, inclusive.
Each element of words will contain between 1 and 50 characters, inclusive.
Each character in each element of words will be a lowercase letter ('a'-'z').
All the elements in words will be pairwise distinct.

Examples

```
{"tokyo", "kyoto"}
```
```
Returns: 1
```
As mentioned in the problem statement, ("tokyo", "kyoto") is an interesting pair.
```
{"aaaaa", "bbbbb"}
```
```
Returns: 0
```
("aaaaa", "bbbbb") is not an interesting pair.
```
{"ababab","bababa","aaabbb"}
```
```
Returns: 1
```
There is one interesting pair: ("ababab","bababa"). Note that for this interesting pair there is more than one way to choose the strings A and B.
```
{"eel", "ele", "lee"}
```
```
Returns: 3
```

{"aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"}

Returns: 6

```
{"top","coder"}
```
```
Returns: 0
```
Different elements of words may have different lengths.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.