Connection Status:
Competition Arena > FarStrings

FarStrings

SRM 617 · 2013-12-22 · by ir5

SRM 617 · 2013-12-22 · by ir5 · Dynamic Programming, String Manipulation
Class Name: FarStrings
Return Type: String[]
Method Name: find
Arg Types: (string)
Problem Statement

Problem Statement

All strings in this problem are strings of lowercase English letters ('a'-'z').

Given two strings S and T, their edit distance is defined as the smallest number of steps in which we can change S to T. In each step, we are allowed to make one of the following changes:
  • Erasing one arbitrary character of S.
  • Inserting one arbitrary character anywhere into S (including its beginning or end).
  • Replacing one arbitrary character of S by a different character.

For example:
  • The edit distance between "color" and "coord" is 2.
  • The edit distance between "banana" and "bnn" is 3.
  • The edit distance between "aaaa" and "bbbb" is 4.

You are given a String t. Let n be the length of t. Return a String[] with n elements. For each i, element i (0-based index) of the returned String[] must be the lexicographically smallest string with n characters such that the edit distance between t and the string is exactly i+1.

Notes

  • You may assume that for each valid test case there is at least one n-character string with each of the required edit distances.

Constraints

  • t will contain between 1 and 25 characters, inclusive.
  • Each character in t will be a lowercase English letter ('a'-'z').
Examples
0)
"atan"
Returns: {"aaan", "aaaa", "aaba", "babb" }

Let d(s,u) denote the edit distance between the strings s and u. The return value shown above is correct because: d("atan", "aaan") = 1: we can change 't' to 'a'. d("atan", "aaaa") = 2: we can change 't' to 'a' and then 'n' to 'a'. d("atan", "aaba") = 3: one shortest sequence of changes is "atan" -> "aan" -> "aab" -> "aaba". d("atan", "babb") = 4: one shortest sequence of changes is "atan" -> "aan" -> "ban" -> "bab" -> "babb". The strings "aaan", "aaaa", "aaba", and "babb" are the lexicographically smallest strings with the given edit distance from "atan".

1)
"ir"
Returns: {"ar", "aa" }
2)
"aaa"
Returns: {"aab", "abb", "bbb" }
3)
"bazinga"
Returns: {"aazinga", "aaainga", "aaaanga", "aaaaaga", "aaaaaaa", "aaaaaab", "abbaabb" }
4)
"bcdab"
Returns: {"acdab", "aadab", "aaaab", "aaaaa", "aaaca" }

Submissions are judged against all 163 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FarStrings with a public method vector<string> find(string t) · 163 test cases · 2 s / 256 MB per case

Submitting as anonymous