DP
BAN USERScott's solution in Go lang:
I assume it is O(n x m), where n is length of string and m is length of set
func SearchSubstring(arr []rune, str string) string{
matchedCount := 0
hash := make(map[rune]int)
result := ""
start := 0
minLen := len(str) + 1
for i := 0 ; i < len(str); i++ {
for j, _ := range arr {
ch := rune(str[i])
if ch == arr[j] {
if hash[ch] == 0 {
matchedCount++
}
total = total + 1
hash[ch] = hash[ch] + 1
break
}
}
for matchedCount == len(arr) {
// Record substring and its length
if i - start + 1 < minLen {
minLen = i - start + 1
result = str[start: i + 1]
}
// If it is the shortest substring possible, then stop and return
if minLen == len(arr) {
return result
}
ch := rune(str[start])
if v, ok := hash[ch]; ok {
if v == 1 {
matchedCount--
}
total = total - 1
hash[ch] = hash[ch] -1
}
start++
}
}
return result
}
Go implementation
package main
import "fmt"
func main() {
arr := []string {
"Selena",
"Miley",
"Justin",
"Katy",
"Taylor",
}
findCelebrity(arr)
}
func findCelebrity(arr []string) {
index := 0
for i := 1; i < len(arr); i++ {
if knows(index, i) || !knows(i, index) {
index = i
}
}
for i := 0; i < index; i++ {
if knows(index, i) || !knows(i, index) {
fmt.Println("No celebrity found")
return
}
}
fmt.Println(arr[index], "is the celebrity")
}
func knows(a, b int) bool {
arr := [][]uint8{
{ 1, 0, 1, 1, 0 },
{ 1, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 1 },
}
return arr[a][b] > 0
}
Similar implementation in golang:
func main() {
arr := [4][4]uint8 {
{'a', 's','f', 's'},
{'h', 'w','i', 't'},
{'c', 't','a', 'g'},
{'e', 'r','i', 'n'},
}
fmt.Println(wordExists(arr, "waits"))
fmt.Println(wordExists(arr, "waiter"))
fmt.Println(wordExists(arr, "swift"))
fmt.Println(wordExists(arr, "waiting"))
}
func wordExists(arr [4][4]uint8, word string) bool {
index := 0
var visited [4][4]bool
for i := 0 ; i < 4; i++ {
for j := 0 ; j < 4; j++ {
if arr[i][j] == word[index] {
visited[i][j] = true
if lookupNextChar(i, j, word, index + 1, visited, arr) {
return true
}
visited[i][j] = false
}
}
}
return false
}
func lookupNextChar(x, y int, word string, index int, visited [4][4]bool, arr [4][4]uint8) bool {
if index == len(word) {
return true
}
for i := x-1; i <= x+1; i++ {
for j := y-1; j <= y+1; j++ {
if isValidIndex(i, j) && visited[i][j] == false && arr[i][j] == word[index] {
visited[i][j] = true
if lookupNextChar(i, j, word, index + 1, visited, arr) {
return true
}
visited[i][j] = false
}
}
}
return false
}
func isValidIndex( i, j int) bool {
return i >= 0 && i < 4 && j >= 0 && j < 4
}
Go implementation
func Reverse(s string) string {
var startIndex int
var returnString string
for i,v := range s {
if v == ' ' {
returnString = fmt.Sprintf(" %v%v", s[startIndex:i], returnString)
startIndex = i + 1
}
}
returnString = s[startIndex:] + returnString
return returnString
}
Taylor, your implementation is not going to work. What if the bug is introduced by the mid index. You start the next BinarySearch from 0 to mid -1 and end up returning mid-2 instead of mid.
- DP February 22, 2015