Daily Coding Problem: Problem #685

import java.util.* /** * This problem was asked by Facebook. Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters. For example, given "hello/world:here", return "here/world:hello" Follow-up: Does your solution work for the following cases: "hello/world:here/", "hello//world:here" * */ class Problem_685 { /* * solution: Queue+Stack, Time:O(n), Space:O(n) * */ fun delimitersReverse(s: String, delimiters: CharArray): String { val queueForDelimiter = LinkedList<Char>() val words = Stack<String>() //store the position for delimiter have seen var lastIndex = 0 var i = 0 while (i < s.length) { val char = s[i] //meet a delimiter if (char in delimiters) { //avoid add empty space if (i - lastIndex > 1) { words.add(s.substring(lastIndex, i)) } queueForDelimiter.offer(char) //update lastIndex lastIndex = i + 1 } i++ } //check for a word with no last delimiter if (s.last() != queueForDelimiter.first) { words.add(s.substring(lastIndex, i)) } val result = StringBuilder() //set up for result //because words is longer than delimiters while (words.isNotEmpty()) { if (words.isNotEmpty()) { result.append(words.pop()) } if (queueForDelimiter.isNotEmpty()) { val poped = queueForDelimiter.pop() result.append(poped) //check if need insert two same delimiter at same time if (poped == queueForDelimiter.peek()) { result.append(queueForDelimiter.pop()) } } } return result.toString() } }