Substring with Concatenation of All Words
Function Name: findSubstring
Description
Write a function `findSubstring(s, words)` that takes a string `s` and an array of strings `words` as parameters.
All strings in `words` are of the same length.
The function should return all starting indices in `s` where a concatenation of each word in `words` exactly once forms a substring.
The indices should be returned in ascending order.
The function should handle overlapping words and words can appear in any order.
Requirements
- The function should take two parameters: a string `s` and an array of strings `words`.
- A valid 'word' consists of letters only.
- Assume all words are the same length.
- The function should return a list of integers representing starting indices.
- If no concatenation forms a substring, return an empty list.
- The function should run in polynomial time complexity or better.
Examples
Given `s` = 'barfoothefoobarman' and `words` = ['foo', 'bar'], `findSubstring(s, words)` should return `[0, 9]` since 'barfoo' and 'foobar' can be formed by concatenating 'foo' and 'bar'.Given `s` = 'wordgoodgoodgoodbestword' and `words` = ['word','good','best','word'], `findSubstring(s, words)` should return `[]` because 'word' is repeated, making it impossible to form a valid substring with each word used exactly once.
Links
K-nearest Points to Origin
Sat Oct 12 2024
Write a function that finds the 'k' nearest points to the origin (0, 0) in a 2D plane. The points are provided as a list of tuples (x, y), representing the cartesian coordinates of the points. You should return a list of 'k' tuples that are closest to the origin, sorted by their Euclidean distance from the origin. In case of a tie in distances, sort the points by their x-coordinates, and if those are the same, by their y-coordinates.
Binary Tree Paths
Mon Oct 14 2024
Write a function that returns all the paths from the root to leaf nodes in a binary tree. A path is defined as a sequence of nodes starting from the root node and ending at any leaf node. The function should output the paths as an array of string representations, where each string contains the path's nodes' values separated by '->'. Your function should work with any binary tree, not necessarily a binary search tree.