WordPattern
SRM 248 · 2005-06-21 · by NeverMore
SRM 248 · 2005-06-21 · by NeverMore · Simple Search, Iteration
Problem Statement
Problem Statement
One day, I started writing out the following patterns (The procedure for constructing the pattern is deliberately not given, you must infer the procedure through the examples):
Input string: "HELLO" (quotes for clarity only)Pattern: O OLO OLLLO OLLELLO OLLEHELLO OLLELLO OLLLO OLO O
Input string: "TC" (quotes for clarity only)Pattern: C CTC C
Input string: "ABCD" (quotes for clarity only)Pattern: D DCD DCBCD DCBABCD DCBCD DCD D
After constructing the patterns, I noticed something interesting. Starting with the first letter of the input string (which appears only once in the very center of the pattern), I can trace a path outwards toward the edges, spelling out the original input string. Of course, I only move Up, Down, Left and Right from any letter. I'm now perplexed because I want to know how many ways the original input string can be spelled out in the pattern. I must always end at an edge, and I can't go over one letter more than once while spelling a word.
Create a class WordPattern containing the method countWords which takes aString word as input. The method should return along which is the number of ways the original input can be spelled out in the pattern according to my rules.
Notes
- Remember, I only move Up, Down, Left and Right from any letter to the next letter and never use a letter twice.
Constraints
- word will contain between 1 and 50 characters inclusive.
- word will contain only uppercase letters ('A'-'Z').
Examples
0)
"HELLO" Returns: 60
1)
"TC" Returns: 4
2)
"ABCDEFGHIJKLMNOPQRST" Returns: 2097148
3)
"ALKSJDLGHSDGH" Returns: 16380
4)
"SDG" Returns: 12
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WordPattern with a public method long long countWords(string word) · 72 test cases · 2 s / 256 MB per case