[Go] Array and string - Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

 

My code

func longestCommonPrefix(strs []string) string {
	shortest := 201
	short := ""
	longest := ""
	buf := ""
	for _, v := range strs {
		if len(v) < shortest {
			shortest = len(v)
			short = v
		}
	}

	for i := shortest; i > 0; i-- {
		length := i
		right := 0

		for _, v := range strs {
			temp := v
			for j := 0; j < len(temp); j++ {
				if j+length > len(temp) {
					break
				}
				if temp[0:j+length] == short[0:i] {
					right++
					buf = short[0:i]
				}
			}
			if right == len(strs) && len(longest) < len(buf) {
				longest = buf
			}

		}

	}
	return longest
}

- I declared shortest to allocate length of shortest string for using standard of prefix.

- This variable is 201 because maximum length of string is 200.

- Short will have shortest string.

- longest will have longest prefix after checking buf value.

- First for loop will find shortest string.

- Second for loop will be used for decreasing array length from right to left.

- Length will be used for it.

- Right value will have number of calling.

- For loop in the second for loop runs for calling strings which saved in slice.

- These stings will be allocated to temp for comparing with shortest string.

- Next for loop will be printing string as many words as the shortest word.

- First if condition will screen if printed string is beyond length with common words.

- when first if condition passes, original string and shortest string will be compared.

- If so right will increase and matched string will be allocated to buf.

- Last if condition will check whether every strings are matched with shortest prefix.

- Also buf which came from fomer if condition is longer than it, longest string will have lonager prefix.

 

sample 0 ms submission & sample 2300 KB submission

func longestCommonPrefix(strs []string) string {
    m := 500
    
    for _, s := range strs {
        l := len(s)
        if l < m {
            m = l
        }
    }
    
    prefix := ""
    
    for i:=0; i<m ;i++ {
        test := ""
        
        for j, s := range strs {
            if j==0 {
                test = s[0:i+1]
                continue
            }
            if test != s[0:i+1] {
                test = ""
                break
            }
        }
        
        if test == "" {
            break
        }
        prefix = test
    }
    
    return prefix
}

• m will be 500 and have shortest length after for loop.
• prefix will be declared with ""
• i will increase from 0 to m.
• test variable is declared with "".
• When j index is 0, test will have string s[0:i+1].
• I think i can be 1 and condition same and less than m.
• Next if will compare test with next string [0:1+1].
• I think opposite code will be better.
• For example short length comparison from the saved shortest length to the end.

Modification

func longestCommonPrefix(strs []string) string {
	shortest := 201

	for _, v := range strs {
		if len(v) < shortest {
			shortest = len(v)
		}
	}

	for i := shortest; i > 0; i-- {
		temp := ""
		for j, k := range strs {
			if j == 0 {
				temp = k[0:i]
			}
			if temp != k[0:i] {
				break
			}
			if temp == k[0:i] && j == len(strs)-1 {
				return temp
			}
		}

	}
	return ""
}

sample 1 ms submission

func longestCommonPrefix(strs []string) (prefix string) {
    minLen := math.MaxInt
    
    for _, str := range strs {
        minLen = min(minLen, len(str))
    }
    
    builder := strings.Builder{}
    
    first := strs[0]
    for i := 0; i < minLen; i++ {
        char := first[i]
        for _, str := range strs[1:] {
            if str[i] != char {
                return builder.String()
            }
        }
        builder.WriteByte(char)
    }
    
    return builder.String()
}

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}

sample 2 ms submission

func longestCommonPrefix(strs []string) string {
	prefix := strs[0]
	for i := 1; i < len(strs); i++ {
		for j := 0; j < len(prefix); j++ {
			if len(strs[i]) <= j || strs[i][j] != prefix[j] {
				prefix = prefix[0:j]
				break
			}
		}
	}
	return prefix
}

sample 3 ms submission

func longestCommonPrefix(strs []string) string {
    res := -1
    for {
        done := false
        for i := 0; i < len(strs); i++ {
            if res == len(strs[i]) - 1 {
                done = true
                break
            }
            if i > 0 && strs[i - 1][res + 1] != strs[i][res + 1] {
                done = true
                break
            }
        }
        if done {
            break
        } 
        res++
    }
    if res == -1 {
        return ""
    }
    return strs[0][:res + 1]
}

sample 4 ms submission

func min(x, y int) int {
  if x < y {
    return x
  }
  
  return y
}

func commonPrefix(str1 string, str2 string) string {
  prefix := ""  
  size := min(len(str1), len(str2))
  
  for i:= 0; i < size; i++ {
    if str1[i] != str2[i] {
      break
    }
    
    prefix += string(str1[i])
  }
  
  return prefix
}

func longestCommonPrefix(strs []string) string {
  if len(strs) == 0 {
    return ""
  }

  prefix := strs[0]
  
  for i:= 1; i < len(strs); i++ {
    prefix = commonPrefix(prefix, strs[i])
  }
  
  return prefix  
}

sample 2200 KB submission

func longestCommonPrefix(strs []string) string {
    if len(strs) == 1 {
		return strs[0]
	}

	start, end := 0, len(strs[0])
	for start < end {
		flag := true
		for i := 1; i < len(strs); i++ {
			if start >= len(strs[i]) || strs[i][start] != strs[0][start] {
				flag = false
				break
			}
		}

		if flag {
			start++
		} else {
			break
		}
	}

	return strs[0][:start]
}

sample 2400 KB submission

func longestCommonPrefix(strs []string) string {
	longestPrefix := ""
	done := false
	if len(strs) < 1 {
		return ""
	} else if len(strs) == 1 {
		return strs[0]
	}

	for idx := 0; idx < len(strs[0]) && !done; idx++ {
		currentChar := strs[0][idx]
		for _, word := range strs {
			if len(word) <= idx || word[idx] != currentChar {
				done = true
				break
			}
		}
		if !done {
			longestPrefix += string(currentChar)
		}
	}

	return longestPrefix    
}