gcdOfStrings

gistfile1.kt

fun gcdOfStrings(str1: String, str2: String): String {
  // find the shorter string
  var short: String
  val long: String

  if (str1.length > str2.length) {
    short = str2
    long = str1
  } else {
    short = str1
    long = str2
  }

  // find all prefixes from the shorter string
  // TODO: we can improve this to find "tryable" prefixes (e.g. divide the short str by 2 ?)
  val mutableList = mutableListOf<String>()
  for (i in short.length downTo 0) {
    mutableList.add(short.substring(0, i))
  }

  // iterating from the largest prefix
  var result: String = ""
  for (prefix in mutableList) {
    if (prefix.isEmpty())
      break
    if (isDivisible(short, prefix) && isDivisible(long, prefix)) {
      result = prefix
      break
    }
  }
  // return the string if found
  return result
}

// recursion function to determine if str is divisible by the prefix
fun isDivisible(str: String, prefix: String): Boolean {
  if (str.isEmpty())  // reached an end
    return true
  if (!str.startsWith(prefix))  // not divisible
    return false
  else
    return isDivisible(str.substringAfter(prefix), prefix)  // keep recursion
}