Skip to content

Latest commit

 

History

History
76 lines (50 loc) · 3.1 KB

033.md

File metadata and controls

76 lines (50 loc) · 3.1 KB

1528. Shuffle String

Difficulty: 🟢 Easy

You are given a string s and an integer array indices of the  same length. The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

Examples:

Example 1:

033_01.jpeg

Input: s = "codeleet",indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc",indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Constraints:

  • s.length == indices.length == n
  • 1 <= n <= 100
  • s consists of only lowercase English letters.
  • 0 <= indices[i] < n
  • All values of indices are unique.

Solutions

O(n) solution in Python3

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        mapping = dict(zip(indices, s))
        return "".join([mapping[index] for index in range(len(s))])

The given solution shuffles the string s based on the given indices array by creating a mapping between the indices and the corresponding characters in the original string. It then uses this mapping to generate the shuffled string.

The algorithm works as follows:

  1. Create an empty dictionary, mapping, to store the mapping between indices and characters.
  2. Iterate through the indices array and the characters of the original string s simultaneously:
    • Add a key-value pair to the mapping dictionary, where the index is the key and the character is the value.
  3. Create an empty string, shuffled, to store the shuffled string.
  4. Iterate through the range from 0 to the length of s:
    • Append the character from the mapping dictionary at the corresponding index to the shuffled string.
  5. Return the shuffled string, which represents the shuffled version of the original string.

The algorithm creates a mapping between the indices and characters, and then constructs the shuffled string by retrieving the characters from the mapping based on the indices.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the string s and the indices array. The algorithm iterates through the indices array and the characters of s once, performing constant-time operations at each iteration.

The space complexity of the algorithm is O(n) as it uses additional space to store the mapping dictionary and the shuffled string, each with a maximum size of n.

Summary

The given solution shuffles the string s based on the given indices array by creating a mapping between the indices and characters and then constructing the shuffled string using this mapping. It has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.