CODEWITHSUNDEEP
data-structures
Turtle
Turtle

Reputation: 704

Whats the best data-structure to store a string

Recently I had an interview and I was asked this question.

Given a string which can have insert,delete and substring functions.

substring function returns the string from start index to end index which are given as parameters.

All three options are in random order, what is the efficient data-structure to use.

Upvotes: 3

Views: 1399

Answers (1)

Shihab Shahriar Khan
Shihab Shahriar Khan

Reputation: 5455

I'm assuming insert or delete operations here can be carried out in the middle of the string, not just end. Otherwise anything like c++ vector or python list is good enough.

Otherwise, Rope data structure is a very good candidate. It allows all of those operations in O(logN), which i think the best anyone could hope for. It's a good choice for editors, or while manipulating huge strings, genome data for example.

Another related, and more common choice for editors is Gap Buffer.

Upvotes: 3

Related Questions