[Python3] 95%, two dictionaries and a counter
This is a one-pass algorithm using 2 dictionaries d1 and d2. Both of these relate a valid start string with the required end string. In d1, the keys are the sta
This is a one-pass algorithm using 2 dictionaries ```d1``` and ```d2```. Both of these relate a valid start string with the required end string. In ```d1```, the keys are the starts, and the values are the ends. In ```d2```, the keys are the ends, and the values are the starts. We also maintain a count of each string that we see.\n\nSo our algorithm is:\n* Initialize ```out``` to 0.\n* For each string ```n``` we see:\n\t* Check if ```n``` is a key in ```d1```. If it is, increment ```out``` by the count of  ```d1[n]```.\n\t* Check if ```n``` is a key in ```d2```. If it is, increment ```out``` by the count of  ```d2[n]```.\n\t* Increase the count of ```n``` by 1.\n\t* If ```n``` is a valid start of ```target```, create an entry in ```d2``` where the key is the corresponding end.\n\t* If ```n``` is a valid end of ```target```, create an entry in ```d1``` where the key is the corresponding start.\n* Return ```out```.\n\n```\ndef numOfPairs(self, nums: List[str], target: str) -> int:        \n        d1, d2 = {}, {}\n        counts = Counter()\n        \n        out = 0\n        \n        for n in nums:            \n            if n in d1:\n                out += counts[d1[n]]\n            if n in d2:\n                out += counts[d2[n]]\n            \n            counts[n] += 1\n            \n            l = len(n)\n            \n            if n == target[:l]:\n                d2[target[l:]] = n\n                \n            if n == target[-l:]:\n                d1[target[:-l]] = n\n        \n        return out\n```
['Python3']