We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Hi, I don't know whether this is the good place for this question. But I hope I can get some help here.
My first solution for swap even characters in string is below.
def swapString(s:String):String = s match {
case "" => ""
case _ => s.take(2).reverse + swapString(s drop 2)
}
The code results a runtime error for a very long String.
Second attemp:
def swapString(s:String):String = {
def swapHelper(acc:String, remain:String):String = remain match {
case "" => acc
case _ => swapHelper(acc + remain.take(2).reverse, remain.drop(2))
}
swapHelper("", s)
}
Try to make the tailrec optimization. Time Out
Third attemp:
def swapString(s:String):String = {
def swapHelper(acc:List[Char], remain:List[Char]):List[Char] = remain match {
case Nil => acc
case x :: y :: rest => swapHelper(acc ++ List(y,x), rest)
}
swapHelper(List(), s.toList).mkString("")
}
I thought String.take, String.reverse and String.drop is expensive. And I am aware of string concatenation is a very bad idea. So, I convert String to List. However I still want to make the tailrec optimization. Well this may have to use list concatentation which is also time comsuming. Time out
The pass temp:
def swapString(s:String):String = {
def swapHelper(string:List[Char]):List[Char] = string match {
case Nil => Nil
case x::Nil => List(x)
case x :: y :: rest => y :: x :: swapHelper(rest)
}
swapHelper(s.toList).mkString("")
}
I know List append head is O(1). So, throw away the tailrec optimization. And It finally passed. However I don't think this temp is optimal. It will still invole a lot of function calls for very long string.
My questions:
1. scala data structure choosing. How can I choose the best ds? is There any refrences for the internals of scala data structures.
2. For this problem. I really don't like the idea of convert string to list, compute, then covert list back to string. is there any other smarter ways? And tailrec optimizaition!
3. This kind of in-place replace problem is perfect for mutable arrays. can functional programming get a comparable performace (time and space) for this kind of problem?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
String-o-Permute
You are viewing a single comment's thread. Return to all comments →
Hi, I don't know whether this is the good place for this question. But I hope I can get some help here.
My first solution for swap even characters in string is below.
The code results a runtime error for a very long String.
Second attemp:
Try to make the tailrec optimization. Time Out
Third attemp:
I thought String.take, String.reverse and String.drop is expensive. And I am aware of string concatenation is a very bad idea. So, I convert String to List. However I still want to make the tailrec optimization. Well this may have to use list concatentation which is also time comsuming. Time out
The pass temp:
I know List append head is O(1). So, throw away the tailrec optimization. And It finally passed. However I don't think this temp is optimal. It will still invole a lot of function calls for very long string.
My questions: