leetcodeの"Longest Common Prefix"をgolangで解いてみた

概要

leetcodeのEasy問題の一つ、"Longest Common Prefix"をGoで解いていく。
https://leetcode.com/problems/longest-common-prefix/

解答のプロセス

以下のようなプロセスで解くことを考えた。

1. Input:strsの要素を辞書順にソートする
2. ソートされたstrsの最初の要素と最後の要素を取得する
3. 最初の要素と最後の要素において、頭から何番目までの文字が共通であるかを比較する

1. Input:strsの要素を辞書順にソートする

何故辞書順に並べる必要があるのかを考えてみる。
例えば、strs = ["aaa","aab",aabb","aaaa","ab"]となっているとする。
この配列の要素の共通の文字列は何か？このレベルなら人の目でも数えやすい。答えは"a"である。
これを辞書順に並べ替えたstrs_sortを作成してみる。
strs_sort = ["aaa","aaaa","aab","aabb","ab"] となる。
辞書順であるため、最初と最後の要素を比べれば、それ以外の要素も共通の文字列を持っていることがわかる。
そのため、strsを辞書順にソートする。
strsを辞書順にソートするためにはsort.Strings(strs)を利用する

2. ソートされたstrsの最初の要素と最後の要素を取得する

上記で説明したとおり、最初の要素と最後の要素を取得することで全体の共通の文字列を取得することができる。

3. 最初の要素と最後の要素において、頭から何番目までの文字が共通であるかを比較する

下記のようなコードで確かめることができる。

first_str := strs[0] // strsの最初の要素
last_str := strs[len(strs) - 1] //strsの最後の要素

/* 最初と最後の文字列のどちらが長いかを取得する */
len_str := 0
if len(first_str) < len(last_str) {
	len_str = len(first_str)
} else {
	len_str = len(last_str)
}

/* 共通の文字列の長さを取得する */
common_length := 0 
for i := 0; i < len_str; i++ {
	if first_str[i] == last_str[i] {
		common_length++
	} else {
		break
	}
}

ポイントとしては、最初の要素と最後の要素のどちらが文字列として長いかを考える必要がある。

作成したコード

package main

import (
	"fmt" 
	"sort"
)

func longestCommonPrefix(strs []string) string {
	if len(strs) > 0 {
		sort.Strings(strs)
	}
	first_str := strs[0]
	last_str := strs[len(strs) - 1]
	len_str := 0
	if len(first_str) < len(last_str) {
		len_str = len(first_str)
	} else {
		len_str = len(last_str)
	}
	common_length := 0
	for i := 0; i < len_str; i++ {
		if first_str[i] == last_str[i] {
			common_length++
		} else {
			break
		}
	}
	if common_length == 0 {
		return ""
	} else {
		return first_str[:common_length]
	}
}

func main(){
	strs := []string{"aaa","aab",aabb","aaaa","ab"}
	fmt.Println(longestCommonPrefix(strs))
}

感想

ポイントとしては、

• 辞書順にすることで簡単に比較を行うことができる
• 最初の要素と最後の要素の文字列の長さを比較する